Clique graph recognition is NP-complete

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

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Faria, L., Figueiredo, C. M. H. de, Gutiérrez, Marisa
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Matemática
Planar graph
Complete graph
Intersection graph
Truth assignment
Nonempty intersection
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/132535
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-132535
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
Planar graph
Complete graph
Intersection graph
Truth assignment
Nonempty intersection
spellingShingle Matemática
Planar graph
Complete graph
Intersection graph
Truth assignment
Nonempty intersection
Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
Clique graph recognition is NP-complete
topic_facet Matemática
Planar graph
Complete graph
Intersection graph
Truth assignment
Nonempty intersection
description A complete set of a graph G is a subset of V inducing a complete subgraph. A clique is a maximal complete set. Denote by the clique family of G. The clique graph of G, denoted by K(G), is the intersection graph of . 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. We prove that the clique graph recognition problem is NP-complete.
format Objeto de conferencia
Objeto de conferencia
author Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title Clique graph recognition is NP-complete
title_short Clique graph recognition is NP-complete
title_full Clique graph recognition is NP-complete
title_fullStr Clique graph recognition is NP-complete
title_full_unstemmed Clique graph recognition is NP-complete
title_sort clique graph recognition is np-complete
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/132535
work_keys_str_mv AT alconlilianagraciela cliquegraphrecognitionisnpcomplete
AT farial cliquegraphrecognitionisnpcomplete
AT figueiredocmhde cliquegraphrecognitionisnpcomplete
AT gutierrezmarisa cliquegraphrecognitionisnpcomplete
bdutipo_str Repositorios
_version_ 1764820454082609152

Ejemplares similares