More results on the complexity of identifying problems in graphs

被引：5
|
作者：
Hudry, Olivier [1 ,2 ]
Lobstein, Antoine [1 ,2 ]
机构：
[1] Telecom ParisTech, Inst Telecom, 46 Rue Barrault, F-75634 Paris 13, France
[2] CNRS, LTCI UMR 5141, F-75634 Paris 13, France
来源：
THEORETICAL COMPUTER SCIENCE | 2016年 / 626卷
关键词：
Graph theory; Complexity; Complexity classes; Polynomial hierarchy; NP-completeness; Hardness; Identifying codes; Twin-free graphs; HAMMING-SPACES; CODES;
D O I：
10.1016/j.tcs.2016.01.021
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 subset of V. We locate these problems in the complexity classes of the polynomial hierarchy. (C) 2016 Published by Elsevier B.V.
引用
收藏
页码：1 / 12
页数：12
相关论文
共 50 条
12345