Subir material

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2019-10-03T19:00:18Z
dc.date.available 2019-10-03T19:00:18Z
dc.date.issued 2009
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/82662
dc.description.abstract 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. en
dc.format.extent 2072-2083 es
dc.language en es
dc.subject Clique graphs es
dc.subject Helly property es
dc.subject Intersection graphs es
dc.subject NP-complete problems es
dc.title The complexity of clique graph recognition en
dc.type Articulo es
sedici.identifier.other doi:10.1016/j.tcs.2009.01.018 es
sedici.identifier.other eid:2-s2.0-64249166457 es
sedici.identifier.issn 0304-3975 es
sedici.creator.person Alcón, Liliana Graciela es
sedici.creator.person Faria, Luerbio es
sedici.creator.person Figueiredo, Celina M. H. de es
sedici.creator.person Gutiérrez, Marisa es
sedici.subject.materias Matemática es
sedici.description.fulltext true es
mods.originInfo.place Facultad de Ciencias Exactas es
sedici.subtype Articulo es
sedici.rights.license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-sa/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Theoretical Computer Science es
sedici.relation.journalVolumeAndIssue vol. 410, no. 21-23 es


Descargar archivos

Thumbnail
Documento completo
Descargar archivo (1.494Mb) - PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)