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 条
  • [31] Minimum sizes of identifying codes in graphs differing by one vertex
    Charon, Irene
    Honkala, Iiro
    Hudry, Olivier
    Lobstein, Antoine
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2013, 5 (02): : 119 - 136
  • [32] DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY
    Charbit, Emmanuel
    Charon, Irene
    Cohen, Gerard
    Hudry, Olivier
    Lobstein, Antoine
    ADVANCES IN MATHEMATICS OF COMMUNICATIONS, 2008, 2 (04) : 403 - 420
  • [33] The complexity results of the sparse optimization problems and reverse convex optimization problems
    Jiang, Zhongyi
    Hu, Qiying
    OPTIMIZATION LETTERS, 2020, 14 (08) : 2149 - 2160
  • [34] Minimum sizes of identifying codes in graphs differing by one edge
    Irène Charon
    Iiro Honkala
    Olivier Hudry
    Antoine Lobstein
    Cryptography and Communications, 2014, 6 : 157 - 170
  • [35] The complexity results of the sparse optimization problems and reverse convex optimization problems
    Zhongyi Jiang
    Qiying Hu
    Optimization Letters, 2020, 14 : 2149 - 2160
  • [36] The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem
    Esperet, Louis
    Mazzuoccolo, Giuseppe
    Tarsi, Michael
    JOURNAL OF COMBINATORICS, 2016, 7 (2-3) : 453 - 479
  • [37] Complexity results for storage loading problems with stacking constraints
    Bruns, Florian
    Knust, Sigrid
    Shakhlevich, Natalia V.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 249 (03) : 1074 - 1081
  • [38] New complexity results on array contraction and related problems
    Darte, A
    Huard, G
    JOURNAL OF VLSI SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY, 2005, 40 (01): : 35 - 55
  • [39] New Complexity Results on Array Contraction and Related Problems
    Alain Darte
    Guillaume Huard
    Journal of VLSI signal processing systems for signal, image and video technology, 2005, 40 : 35 - 55
  • [40] Complexity results for flow shop problems with synchronous movement
    Waldherr, Stefan
    Knust, Sigrid
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (01) : 34 - 44
12345