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 条
  • [1] Complexity results for identifying codes in planar graphs
    Auger, David
    Charon, Irene
    Hudry, Olivier
    Lobstein, Antoine
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (06) : 691 - 710
  • [2] On the DISTANCE IDENTIFYING SET Meta-problem and Applications to the Complexity of Identifying Problems on Graphs
    Barbero, Florian
    Isenmann, Lucas
    Thiebaut, Jocelyn
    ALGORITHMICA, 2020, 82 (08) : 2243 - 2266
  • [3] Some rainbow problems in graphs have complexity equivalent to satisfiability problems
    Hudry, Olivier
    Lobstein, Antoine
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2022, 29 (03) : 1547 - 1572
  • [4] More on the complexity of defensive domination in graphs
    Henning, Michael A.
    Pandey, Arti
    Tripathi, Vikash
    DISCRETE APPLIED MATHEMATICS, 2025, 362 : 167 - 179
  • [5] New complexity results for shop scheduling problems with agreement graphs
    Tellache, Nour ElHouda
    THEORETICAL COMPUTER SCIENCE, 2021, 889 : 85 - 95
  • [6] The complexity of dissociation set problems in graphs
    Orlovich, Yury
    Dolgui, Alexandre
    Finke, Gerd
    Gordon, Valery
    Werner, Frank
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (13) : 1352 - 1366
  • [7] Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: Some complexity results
    Benkouar, A
    Manoussakis, Y
    Paschos, VT
    Saad, R
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1996, 30 (04): : 417 - 438
  • [8] The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
    Hu, Fu-Tao
    Sohn, Young
    THEORETICAL COMPUTER SCIENCE, 2014, 535 : 46 - 53
  • [9] Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth
    Addis, Bernardetta
    Di Summa, Marco
    Grosso, Andrea
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2349 - 2360
  • [10] Complexity results on graphs with few cliques
    Rosgen, Bill
    Stewart, Lorna
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2007, 9 (01) : 127 - 135
12345