This HTML5 document contains 40 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

PrefixNamespace IRI
category-eshttp://es.dbpedia.org/resource/Categoría:
dcthttp://purl.org/dc/terms/
n14http://es.wikipedia.org/wiki/Problema_de_la_cobertura_de_cliques?oldid=120128229&ns=
wikipedia-eshttp://es.wikipedia.org/wiki/
n9http://es.dbpedia.org/resource/Computers_and_Intractability:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n12http://www.win.tue.nl/~gwoegi/AC/karp-1971.
dbpedia-eshttp://es.dbpedia.org/resource/
prop-eshttp://es.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5https://web.archive.org/web/20131229110131/http:/www.win.tue.nl/~gwoegi/AC/karp-1971.
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
Subject Item
dbpedia-es:Cobertura_de_cliques
dbo:wikiPageRedirects
dbpedia-es:Problema_de_la_cobertura_de_cliques
Subject Item
dbpedia-es:Problema_de_la_cobertura_de_cliques
rdfs:label
Problema de la cobertura de cliques
rdfs:comment
En teoría de la complejidad computacional, el problema de la cobertura de cliques es un problema de decisión NP-completo de la teoría de grafos. Es uno de los 21 problemas originales que Richard Karp demostró que era NP-completo en su artículo de 1972 «Reducibility Among Combinatorial Problems». El problema relacionado de cobertura de aristas de cliques, que considera conjuntos de cliques que incluyen todas las aristas de un grafo dado, también es NP-completo.
dct:subject
category-es:Problemas_NP-completos category-es:Problemas_computacionales_de_teoría_de_grafos
foaf:isPrimaryTopicOf
wikipedia-es:Problema_de_la_cobertura_de_cliques
prop-es:apellidos
Karp Garey Johnson
prop-es:apellidosEditor
Thatcher Miller
prop-es:año
1979 1972
prop-es:editorial
W. H. Freeman Plenum Press
prop-es:enlaceautor
Michael Garey David S. Johnson Richard Karp
prop-es:fechaacceso
26
prop-es:fechaarchivo
29
prop-es:isbn
0
prop-es:nombre
Richard D. S. M. R.
prop-es:nombreEditor
J. W. R. E.
prop-es:páginas
85
prop-es:serie
Proceedings of a Symposium on the Complexity of Computer Computations
prop-es:título
n9:_A_Guide_to_the_Theory_of_NP-Completeness Reducibility Among Combinatorial Problems
prop-es:url
n12:pdf
prop-es:urlarchivo
n5:pdf
dbo:wikiPageID
6118630
dbo:wikiPageRevisionID
120128229
dbo:wikiPageExternalLink
n12:pdf n5:pdf
dbo:wikiPageLength
2530
prov:wasDerivedFrom
n14:0
dbo:abstract
En teoría de la complejidad computacional, el problema de la cobertura de cliques es un problema de decisión NP-completo de la teoría de grafos. Es uno de los 21 problemas originales que Richard Karp demostró que era NP-completo en su artículo de 1972 «Reducibility Among Combinatorial Problems». El problema consiste en determinar si los vértices de un grafo pueden ser particionados en k cliques. Dada una partición de los vértices en k conjuntos, se puede verificar en tiempo polinómico que cada conjunto forma un clique, de modo que el problema es NP. La NP-completitud se puede demostrar por reducción polinómica a partir del problema de k-coloración de grafos. Para ver esto, basta se transforma una instancia G en el grafo complemento G' . Así, encontrar una partición de G' en k cliques corresponde a encontrar una partición de vértices de G en k conjuntos independientes; a cada uno de estos conjuntos se le puede asignar uno de los k colores. El problema relacionado de cobertura de aristas de cliques, que considera conjuntos de cliques que incluyen todas las aristas de un grafo dado, también es NP-completo.
Subject Item
wikipedia-es:Problema_de_la_cobertura_de_cliques
foaf:primaryTopic
dbpedia-es:Problema_de_la_cobertura_de_cliques