More results on the complexity of identifying problems in graphs

Olivier Hudry; Antoine Lobstein

doi:10.1016/j.tcs.2016.01.021

More results on the complexity of identifying problems in graphs

Olivier Hudry
, Antoine Lobstein

CNRS LTCI

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

6 Citations (Scopus)

Résumé

We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥ 1 and a graph G = (V, E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a subset of vertices X⊂ V. We locate these problems in the complexity classes of the polynomial hierarchy.

langue originale	Anglais
Pages (de - à)	1-12
Nombre de pages	12
journal	Theoretical Computer Science
Volume	626
Les DOIs	https://doi.org/10.1016/j.tcs.2016.01.021
état	Publié - 2 mai 2016
Modification externe	Oui

Accès au document

10.1016/j.tcs.2016.01.021

Contient cette citation

@article{19149bafadf14c96b045cf29de3b62b5,

title = "More results on the complexity of identifying problems in graphs",

abstract = "We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥ 1 and a graph G = (V, E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a subset of vertices X⊂ V. We locate these problems in the complexity classes of the polynomial hierarchy.",

keywords = "Complexity, Complexity classes, Graph theory, Hardness, Identifying codes, NP-completeness, Polynomial hierarchy, Twin-free graphs",

author = "Olivier Hudry and Antoine Lobstein",

note = "Publisher Copyright: {\textcopyright} 2016.",

year = "2016",

month = may,

day = "2",

doi = "10.1016/j.tcs.2016.01.021",

language = "English",

volume = "626",

pages = "1--12",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - More results on the complexity of identifying problems in graphs

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2016/5/2

Y1 - 2016/5/2

N2 - We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥ 1 and a graph G = (V, E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a subset of vertices X⊂ V. We locate these problems in the complexity classes of the polynomial hierarchy.

AB - We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥ 1 and a graph G = (V, E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a subset of vertices X⊂ V. We locate these problems in the complexity classes of the polynomial hierarchy.

KW - Complexity

KW - Complexity classes

KW - Graph theory

KW - Hardness

KW - Identifying codes

KW - NP-completeness

KW - Polynomial hierarchy

KW - Twin-free graphs

U2 - 10.1016/j.tcs.2016.01.021

DO - 10.1016/j.tcs.2016.01.021

M3 - Article

AN - SCOPUS:84977867185

SN - 0304-3975

VL - 626

SP - 1

EP - 12

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

More results on the complexity of identifying problems in graphs

Résumé

Accès au document

Empreinte digitale

Contient cette citation