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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1-12
Number of pages	12
Journal	Theoretical Computer Science
Volume	626
DOIs	https://doi.org/10.1016/j.tcs.2016.01.021
Publication status	Published - 2 May 2016
Externally published	Yes

Keywords

Complexity
Complexity classes
Graph theory
Hardness
Identifying codes
NP-completeness
Polynomial hierarchy
Twin-free graphs

Access to Document

10.1016/j.tcs.2016.01.021

Cite this

@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",

}

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this