On the minimum size of an identifying code over all orientations of a graph

Nathann Cohen 1 Frédéric Havet 2
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : If G be a graph or a digraph, let id(G) be the minimum size of an identifying code of G if one exists, and id(G) = +∞ otherwise. For a graph G, let idor(G) be the minimum of id(D) overall orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G) <= 3/2 id(G) for every graph G. We also show that computing idor(G) is NP-hard, while deciding whether idor(G) <= |V (G)| − k is polynomial-time solvable for every fixed integer k.
Type de document :
Article dans une revue
The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (1), pp.#P1.49
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01765643
Contributeur : Frederic Havet <>
Soumis le : vendredi 13 avril 2018 - 07:17:12
Dernière modification le : lundi 5 novembre 2018 - 15:36:03

Fichier

ejc-idor.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01765643, version 1

Citation

Nathann Cohen, Frédéric Havet. On the minimum size of an identifying code over all orientations of a graph. The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (1), pp.#P1.49. 〈hal-01765643〉

Partager

Métriques

Consultations de la notice

334

Téléchargements de fichiers

39