Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes

Autor
Foucaud, F.
Tipus d'activitat
Article en revista
Revista
Journal of discrete algorithms
Data de publicació
2015-03-01
Volum
31
Pàgina inicial
48
Pàgina final
68
DOI
https://doi.org/10.1016/j.jda.2014.08.004 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/27592 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S1570866714000653 Obrir en finestra nova
Resum
An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identified) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identified, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dom...
Citació
Foucaud, F. Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. "Journal of discrete algorithms", 01 Març 2015, vol. 31, p. 48-68.
Paraules clau
Approximation, Identifying code, Locating-dominating set, NP-completeness, Separating system, Test cover

Participants

  • Foucaud, Florent  (autor)

Arxius