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 条
  • [21] On the complexity of equational problems in CNF
    Pichler, R
    JOURNAL OF SYMBOLIC COMPUTATION, 2003, 36 (1-2) : 235 - 269
  • [22] Complexity of k-rainbow independent domination and some results on the lexicographic product of graphs
    Brezovnik, Simon
    Sumenjak, Tadeja Kraner
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 349 : 214 - 220
  • [23] Complexity Results for Linear XSAT-Problems
    Porschen, Stefan
    Schmidt, Tatjana
    Speckenmeyer, Ewald
    THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2010, PROCEEDINGS, 2010, 6175 : 251 - 263
  • [24] Complexity Results for Some Global Optimization Problems
    Locatelli, M.
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2009, 140 (01) : 93 - 102
  • [25] Algorithms and Complexity Results for Genome Mapping Problems
    Rajaraman, Ashok
    Pereira Zanetti, Joao Paulo
    Manuch, Jan
    Chauve, Cedric
    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2017, 14 (02) : 418 - 430
  • [26] Complexity Results for Some Global Optimization Problems
    M. Locatelli
    Journal of Optimization Theory and Applications, 2009, 140 : 93 - 102
  • [27] Injective edge coloring of product graphs and some complexity results
    Bhanupriy, C. K.
    Dominic, Charles
    Sunitha, M. S.
    FILOMAT, 2023, 37 (12) : 3963 - 3983
  • [28] Yet some more complexity results for default logic
    Ben-Eliyahu-Zohary, R
    ARTIFICIAL INTELLIGENCE, 2002, 139 (01) : 1 - 20
  • [29] Minimum sizes of identifying codes in graphs differing by one vertex
    Irène Charon
    Iiro Honkala
    Olivier Hudry
    Antoine Lobstein
    Cryptography and Communications, 2013, 5 : 119 - 136
  • [30] Minimum sizes of identifying codes in graphs differing by one edge
    Charon, Irene
    Honkala, Iiro
    Hudry, Olivier
    Lobstein, Antoine
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2014, 6 (02): : 157 - 170
12345