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

共 23 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

AUGER D, 2009, ELECT NOTES DISCRETE, V34, P585

[3] Complexity results for identifying codes in planar graphs [J].

Auger, David ;

Charon, Irene ;

Hudry, Olivier ;

Lobstein, Antoine .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (06) :691-710

[4] Minimal identifying codes in trees and planar graphs with large girth [J].

Auger, David .

EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (05) :1372-1384

[5] New identifying codes in the binary Hamming space [J].

Charon, Irene ;

Cohen, Gerard ;

Hudry, Olivier ;

Lobstein, Antoine .

EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (02) :491-501

[6] Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard [J].

Charon, L ;

Hudry, O ;

Lobstein, A .

THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) :2109-2120

[7]

COHEN G, 2001, P DIMACS WORKSH COD, V56, P97

[8]

Foucaud F., 2016, ALGORITHMIC IN PRESS

[9]

Foucaud F., 2012, THESIS U BORDEAUX 1

[10] Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes [J].

Foucaud, Florent .

JOURNAL OF DISCRETE ALGORITHMS, 2015, 31 :48-68

← 1 2 3 →