En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera: Isomorfismo-de-subgrafos(G1, G2) Entrada: Dos grafos G1 y G2. Pregunta: Es G1 isomorfo a un subgrafo de G2? La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique.

Autor
  • Michael R. Garey y David S. Johnson (es)
Año
  • 1979 (xsd:integer)
rdfs:comment
  • En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera: Isomorfismo-de-subgrafos(G1, G2) Entrada: Dos grafos G1 y G2. Pregunta: Es G1 isomorfo a un subgrafo de G2? La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. (es)
Editorial
  • W.H. Freeman (es)
foaf:isPrimaryTopicOf
Isbn
  • 0 (xsd:integer)
rdfs:label
  • Problema de isomorfismo de subgrafos (es)
Is foaf:primaryTopic of
dcterms:subject
Título
prov:wasDerivedFrom
dbpedia-owl:wikiPageID
  • 2633289 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 1863 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 21 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 67171258 (xsd:integer)
prop-latam:wikiPageUsesTemplate
dbpedia-owl:wikiPageWikiLink [20 values]
Is dbpedia-owl:wikiPageWikiLink of