About: Subgraph isomorphism problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatComputationalProblemsInGraphTheory, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FSubgraph_isomorphism_problem

AttributesValues
rdf:type
rdfs:label
  • Problema de isomorfismo de subgrafos
  • Problème de l'isomorphisme de sous-graphes
  • Subgraph isomorphism problem
  • Isomorfismo di sottografi
  • Problema do isomorfismo de subgrafos
  • Problem izomorfizmu podgrafu
  • Задача поиска изоморфного подграфа
rdfs:comment
  • En informatique théorique, le problème de l'isomorphisme de sous-graphes est le problème de décision suivant : étant donné deux graphes G et H, déterminer si G contient un sous-graphe isomorphe à H. C'est une généralisation du problème de l'isomorphisme de graphes.
  • Nella teoria della complessità computazionale, l'isomorfismo di sottografo è un problema decisionale di tipo NP-completo. La descrizione del problema è la seguente: siano dati G1 e G2 due grafi, è G1 isomorfo ad un sottografo di G2? La ricerca del sottografo isomorfo ha applicazioni in chemioinformatica.
  • Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.
  • Problem izomorfizmu podgrafu – przykład NP-zupełnego problemu decyzyjnego. Formalna definicja tego problemu wygląda następująco: Dla podanych grafów G i F określić czy istnieje podgraf G izomorficzny z F. Problem ten występuje w przy wyszukiwaniu związków chemicznych zawierających określone podstruktury. Do wyszukiwania takich podstruktur używane są zapytania w formacie SMARTS (stanowiącym rozszerzenie formatu SMILES).
  • Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.
foaf:depiction
  • External Image
  • External Image
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
gold:hypernym
prov:wasDerivedFrom
Faceted Search & Find service v1.17_git93 as of Oct 15 2021


Alternative Linked Data Documents: PivotViewer | ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3322 as of Oct 25 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (62 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software