Subir material

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

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2022-03-14T16:01:35Z
dc.date.available 2022-03-14T16:01:35Z
dc.date.issued 2006
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/132535
dc.description.abstract 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. en
dc.format.extent 269-277 es
dc.language en es
dc.subject Planar graph es
dc.subject Complete graph es
dc.subject Intersection graph es
dc.subject Truth assignment es
dc.subject Nonempty intersection es
dc.title Clique graph recognition is NP-complete en
dc.type Objeto de conferencia es
sedici.identifier.other doi:10.1007/11917496_24 es
sedici.identifier.issn 0302-9743 es
sedici.identifier.issn 1611-3349 es
sedici.identifier.isbn 978-3-540-48382-3 es
sedici.creator.person Alcón, Liliana Graciela es
sedici.creator.person Faria, L. es
sedici.creator.person Figueiredo, C. 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 Objeto de conferencia 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.date.exposure 2006
sedici.relation.event 32nd International Workshop (WG 2006) (Bergen, Norway, June 22-24, 2006) es
sedici.description.peerReview peer-review es
sedici.relation.bookTitle Graph-Theoretic Concepts in Computer Science es


Descargar archivos

Thumbnail
Documento completo
Descargar archivo (943.1Kb) - 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)