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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n30http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n23https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n22http://4mhz.de/cook.html%7Cdoi=10.1145/
dbpedia-srhttp://sr.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
n5http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdf%7Carxiv=cs.DS/9911003%7Cdoi=10.7155/

Statements

Subject Item
dbr:Subgraph_isomorphism_problem
rdf:type
yago:Difficulty114408086 dbo:Agent yago:Algorithm105847438 yago:Attribute100024264 yago:WikicatNP-completeProblems yago:Condition113920835 yago:YagoPermanentlyLocatedEntity yago:Act100030358 yago:Rule105846932 yago:PsychologicalFeature100023100 yago:Event100029378 yago:Activity100407535 yago:Problem114410605 yago:WikicatGraphAlgorithms yago:Procedure101023820 yago:WikicatComputationalProblemsInGraphTheory yago:Abstraction100002137 yago:State100024720
rdfs:label
Problem izomorfizmu podgrafu Isomorfismo di sottografi Problème de l'isomorphisme de sous-graphes Subgraph isomorphism problem Задача поиска изоморфного подграфа Problema do isomorfismo de subgrafos Задача пошуку ізоморфного підграфа Problema de isomorfismo de subgrafos
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: 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í. Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час. 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. Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo. 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. Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время. 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). 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.
dcterms:subject
dbc:Computational_problems_in_graph_theory dbc:NP-complete_problems dbc:Graph_algorithms
dbo:wikiPageID
450062
dbo:wikiPageRevisionID
1082633906
dbo:wikiPageWikiLink
dbr:Computer-aided_design dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Cheminformatics dbr:Maximum_common_subgraph_isomorphism_problem dbr:Smiles_arbitrary_target_specification dbc:Computational_problems_in_graph_theory dbr:Frequent_subtree_mining dbr:Maximum_common_edge_subgraph_problem dbr:Electronic_circuits dbr:Polynomial-time_many-one_reduction dbr:Theoretical_computer_science dbr:Journal_of_Experimental_Algorithmics dbr:Exponential_random_graph dbr:Journal_of_the_ACM dbr:Structure_mining dbr:Artificial_intelligence dbr:Bioinformatics dbr:Graph_rewriting dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Structure_editor dbc:NP-complete_problems dbr:Social_network dbr:Bijection dbr:Undirected_graph dbr:Hamiltonian_path_problem dbr:Induced_subgraph_isomorphism_problem dbc:Graph_algorithms dbr:Pattern_matching dbr:NP-complete dbr:Hamiltonian_cycle dbr:Linear_time dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Query_complexity dbr:SMILES dbr:Clique_problem dbr:Planar_graphs dbr:Bounded_expansion dbr:Decision_problem dbr:Glossary_of_graph_theory dbr:Planar_graph dbr:Complete_graph
dbo:wikiPageExternalLink
n5:jgaa.00014 n22:800157.805047%7Ctitle-link=Symposium n30:Groger_1992_ActaCybernetica.pdf
owl:sameAs
dbpedia-uk:Задача_пошуку_ізоморфного_підграфа dbpedia-pt:Problema_do_isomorfismo_de_subgrafos dbpedia-it:Isomorfismo_di_sottografi dbpedia-ru:Задача_поиска_изоморфного_подграфа freebase:m.029xb6 dbpedia-vi:Bài_toán_đồ_thị_con_đẳng_cấu yago-res:Subgraph_isomorphism_problem dbpedia-pl:Problem_izomorfizmu_podgrafu n23:2P2cc dbpedia-sr:Проблем_изоморфизма_графа dbpedia-es:Problema_de_isomorfismo_de_subgrafos dbpedia-fr:Problème_de_l'isomorphisme_de_sous-graphes wikidata:Q2528185
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Reflist dbt:Harvtxt
dbo:abstract
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 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. 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 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í. Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час. 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. Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo. Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время. Иногда также используется название сопоставление подграфа для той же задачи. Это название делает упор на поиске таких подграфов, а не просто на разрешимости.
gold:hypernym
dbr:Task
prov:wasDerivedFrom
wikipedia-en:Subgraph_isomorphism_problem?oldid=1082633906&ns=0
dbo:wikiPageLength
14493
foaf:isPrimaryTopicOf
wikipedia-en:Subgraph_isomorphism_problem