The complexity of clique graph recognition

被引：20
作者：
Alcon, Liliana
Faria, Luerbio [3 ]
de Figueiredo, Celina M. H. [1 ]
Gutierrez, Marisa [2 ]
机构：
[1] Univ Fed Rio de Janeiro, COPPE, Programa Engn Sistemas & Computacao, Rio de Janeiro, Brazil
[2] UNLP, Dept Matemat, CONICET, La Plata, Buenos Aires, Argentina
[3] Univ Estado Rio De Janeiro, FFP, Dept Matemat, Rio De Janeiro, Brazil
来源：
THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 21-23期
关键词：
Clique graphs; NP-complete problems; Helly property; Intersection graphs; DIAMETERS;
D O I：
10.1016/j.tcs.2009.01.018
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote bye(G) the clique family of G. The clique graph of G, denoted by C(G), is the intersection graph of C(G). Say that G is a clique graph if there exists a graph H such that G = K(H). The clique graph recognition problem asks whether a given graph is a clique graph. A sufficient condition was given by Hamelink in 1968, and a characterization was proposed by Roberts and Spencer in 1971. However, the time complexity of the problem of recognizing clique graphs is a long-standing open question. We prove that the clique graph recognition problem is NP-complete. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：2072 / 2083
页数：12
相关论文
共 39 条
  • [1] Alcón L, 2006, LECT NOTES COMPUT SC, V4271, P269
  • [2] Cliques and extended triangles.: A necessary condition for planar clique graphs
    Alcón, L
    Gutierrez, M
    [J]. DISCRETE APPLIED MATHEMATICS, 2004, 141 (1-3) : 3 - 17
  • [3] Alcon L., 2003, Mat. Contemporanea, V25, P1
  • [4] Clique-critical graphs:: Maximum size and recognition
    Alcon, Liliana
    [J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) : 1799 - 1802
  • [5] [Anonymous], 1971, J. Comb. Theory Series B
  • [6] [Anonymous], SIAM MONOGR DISCRETE
  • [7] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [8] BALAKRISHNAN R, 1986, UTILITAS MATHEMATICA, V29, P263
  • [9] BERGE C, 1987, HYPERGRAPHES
  • [10] Self-clique graphs and matrix permutations
    Bondy, A
    Durán, G
    Lin, MC
    Szwarcfiter, JL
    [J]. JOURNAL OF GRAPH THEORY, 2003, 44 (03) : 178 - 192
1234