The complexity of clique graph recognition

A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote by C (G) the clique family of G. The clique graph of G, denoted by K (G), is the intersection graph of C (G). Say that G is a clique graph if there exists a graph H such that...

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Faria, Luerbio, Figueiredo, Celina M. H. de, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2009
Materias:
Matemática
Clique graphs
Helly property
Intersection graphs
NP-complete problems
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/82662
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-82662
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Clique graphs
Helly property
Intersection graphs
NP-complete problems
spellingShingle Matemática
Clique graphs
Helly property
Intersection graphs
NP-complete problems
Alcón, Liliana Graciela
Faria, Luerbio
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
The complexity of clique graph recognition
topic_facet Matemática
Clique graphs
Helly property
Intersection graphs
NP-complete problems
description A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote by C (G) the clique family of G. The clique graph of G, denoted by K (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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Faria, Luerbio
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Faria, Luerbio
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title The complexity of clique graph recognition
title_short The complexity of clique graph recognition
title_full The complexity of clique graph recognition
title_fullStr The complexity of clique graph recognition
title_full_unstemmed The complexity of clique graph recognition
title_sort complexity of clique graph recognition
publishDate 2009
url http://sedici.unlp.edu.ar/handle/10915/82662
work_keys_str_mv AT alconlilianagraciela thecomplexityofcliquegraphrecognition
AT farialuerbio thecomplexityofcliquegraphrecognition
AT figueiredocelinamhde thecomplexityofcliquegraphrecognition
AT gutierrezmarisa thecomplexityofcliquegraphrecognition
AT alconlilianagraciela complexityofcliquegraphrecognition
AT farialuerbio complexityofcliquegraphrecognition
AT figueiredocelinamhde complexityofcliquegraphrecognition
AT gutierrezmarisa complexityofcliquegraphrecognition
bdutipo_str Repositorios
_version_ 1764820488500019202

Ejemplares similares