Subgraph isomorphism problem (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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: La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. Si el Problema de isomorfismo de subgrafos fuese polinomial, podría utilizarse para resolver el Problema de la clique, también en tiempo polinomial. Sea n el número de aristas de G, se puede ejecutar el problema de isomorfismo de subgrafos n-2 veces (siendo G1 una clique de tamaño 3 a n, y G2 siendo G) para encontrar el clique más grande en G. 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) 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) 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. Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem. (en) 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) 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). Uogólnieniem tego problemu jest optymalizacyjny NP-zupełny problem maksymalnego wspólnego podgrafu, polegający na znalezieniu izomorficznych do siebie podgrafów G i F o maksymalnej wielkości (pl) Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo. (pt) Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время. Иногда также используется название сопоставление подграфа для той же задачи. Это название делает упор на поиске таких подграфов, а не просто на разрешимости. (ru) Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час. (uk) |
| dbo:wikiPageExternalLink | 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 |
| dbo:wikiPageID | 450062 (xsd:integer) |
| dbo:wikiPageLength | 14493 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1082633906 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Undirected_graph dbr:Decision_problem dbr:Induced_subgraph_isomorphism_problem dbr:Electronic_circuits dbr:Smiles_arbitrary_target_specification dbc:NP-complete_problems dbr:Complete_graph dbr:SMILES dbr:Cheminformatics dbr:Social_network dbr:Maximum_common_edge_subgraph_problem dbr:Clique_problem dbr:Glossary_of_graph_theory dbr:Bounded_expansion dbr:NP-complete dbr:Linear_time dbr:Computer-aided_design dbr:Hamiltonian_path_problem dbr:Theoretical_computer_science dbc:Graph_algorithms dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_rewriting dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Journal_of_the_ACM dbr:Maximum_common_subgraph_isomorphism_problem dbr:Artificial_intelligence dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Bijection dbr:Bioinformatics dbc:Computational_problems_in_graph_theory dbr:Planar_graph dbr:Planar_graphs dbr:Frequent_subtree_mining dbr:Pattern_matching dbr:Structure_mining dbr:Structure_editor dbr:Hamiltonian_cycle dbr:Polynomial-time_many-one_reduction dbr:Query_complexity dbr:Exponential_random_graph dbr:Journal_of_Experimental_Algorithmics |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist |
| dcterms:subject | dbc:NP-complete_problems dbc:Graph_algorithms dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Task |
| rdf:type | dbo: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: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) |
| 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) |
| owl:sameAs | freebase:Subgraph isomorphism problem yago-res:Subgraph isomorphism problem wikidata:Subgraph isomorphism problem dbpedia-es:Subgraph isomorphism problem dbpedia-fr:Subgraph isomorphism problem dbpedia-it:Subgraph isomorphism problem dbpedia-pl:Subgraph isomorphism problem dbpedia-pt:Subgraph isomorphism problem dbpedia-ru:Subgraph isomorphism problem dbpedia-sr:Subgraph isomorphism problem dbpedia-uk:Subgraph isomorphism problem dbpedia-vi:Subgraph isomorphism problem https://global.dbpedia.org/id/2P2cc |
| prov:wasDerivedFrom | wikipedia-en:Subgraph_isomorphism_problem?oldid=1082633906&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Subgraph_isomorphism_problem |
| is dbo:wikiPageRedirects of | dbr:Algorithms_for_solving_subgraph_isomorphism_problems dbr:Methods_for_solving_subgraph_isomorphism_problems dbr:Subgraph_isomorphism dbr:Subgraph_matching dbr:Substructure_search |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:NP_(complexity) dbr:Induced_subgraph dbr:Induced_subgraph_isomorphism_problem dbr:Matching_(graph_theory) dbr:Graph-tool dbr:Graph_removal_lemma dbr:Bounded_expansion dbr:Logic_of_graphs dbr:Maximum_common_edge_subgraph dbr:Maximum_common_induced_subgraph dbr:Forbidden_subgraph_problem dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_matching dbr:Graph_rewriting dbr:Graph_theory dbr:List_of_NP-complete_problems dbr:Frequent_subtree_mining dbr:Algorithms_for_solving_subgraph_isomorphism_problems dbr:Methods_for_solving_subgraph_isomorphism_problems dbr:NP-completeness dbr:Structured_program_theorem dbr:Subgraph_isomorphism dbr:Subgraph_matching dbr:Substructure_search |
| is foaf:primaryTopic of | wikipedia-en:Subgraph_isomorphism_problem |