About: Subgraph isomorphism problem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Subgraph isomorphism problem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:State100024720, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FSubgraph_isomorphism_problem

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

Attributes	Values
rdf:type	agent yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720
rdfs:label	Problema de isomorfismo de subgrafos (es) Problème de l'isomorphisme de sous-graphes (fr) Isomorfismo di sottografi (it) Problem izomorfizmu podgrafu (pl) Subgraph isomorphism problem (en) Задача поиска изоморфного подграфа (ru) Problema do isomorfismo de subgrafos (pt) Задача пошуку ізоморфного підграфа (uk)
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. (fr) 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. (it) Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo. (pt) Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час. (uk) 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: Este problema es una generalización del posiblemente más sencillo Problema de isomorfismo de grafos, en el sentido que si este último es NP-completo, entonces la jerarquía polinómica colapsa, así que se supone que no debería ser así. (es) In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time. (en) 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). (pl) Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время. (ru)
dcterms:subject	NP-complete problems Graph algorithms Computational problems in graph theory
Wikipage page ID	450062 (xsd:integer)
Wikipage revision ID	1082633906 (xsd:integer)
Link from a Wikipage to another Wikipage	Undirected graph Decision problem Induced subgraph isomorphism problem Electronic circuits Smiles arbitrary target specification NP-complete problems Complete graph SMILES Cheminformatics Social network Maximum common edge subgraph problem Clique problem Glossary of graph theory Bounded expansion NP-complete Linear time Computer-aided design Hamiltonian path problem Theoretical computer science Graph algorithms Graph isomorphism Graph isomorphism problem Graph rewriting Journal of Graph Algorithms and Applications Journal of the ACM Maximum common subgraph isomorphism problem Artificial intelligence Aanderaa–Karp–Rosenberg conjecture Bijection Bioinformatics Computational problems in graph theory Planar graph Planar graphs Frequent subtree mining Pattern matching Structure mining Structure editor Hamiltonian cycle Polynomial-time many-one reduction Query complexity dbr:Exponential_random_graph dbr:Journal_of_Experimental_Algorithmics
Link from a Wikipage to an external page	http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf http://4mhz.de/cook.html%7Cdoi=10.1145/800157.805047%7Ctitle-link=Symposium http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdf%7Carxiv=cs.DS/9911003%7Cdoi=10.7155/jgaa.00014
sameAs	Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem Subgraph isomorphism problem
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harvtxt dbt:Reflist

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software