Subgraph isomorphism problem
http://dbpedia.org/resource/Subgraph_isomorphism_problem an entity of type: Agent
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.
rdf:langString
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.
rdf:langString
Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.
rdf:langString
Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час.
rdf:langString
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í.
rdf:langString
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.
rdf:langString
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).
rdf:langString
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.
rdf:langString
rdf:langString
Problema de isomorfismo de subgrafos
rdf:langString
Problème de l'isomorphisme de sous-graphes
rdf:langString
Isomorfismo di sottografi
rdf:langString
Problem izomorfizmu podgrafu
rdf:langString
Subgraph isomorphism problem
rdf:langString
Задача поиска изоморфного подграфа
rdf:langString
Problema do isomorfismo de subgrafos
rdf:langString
Задача пошуку ізоморфного підграфа
xsd:integer
450062
xsd:integer
1082633906
rdf:langString
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í.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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
rdf:langString
Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.
rdf:langString
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время. Иногда также используется название сопоставление подграфа для той же задачи. Это название делает упор на поиске таких подграфов, а не просто на разрешимости.
rdf:langString
Задача пошуку ізоморфного підграфа — обчислювальна задача, в якій входом є два графи і і потрібно визначити, чи містить підграф, ізоморфний графу . Задача є узагальненням як задачі про найбільшу кліку, так і задачі про перевірку, чи містить граф гамільтонів цикл, тому є NP-повною. Проте, з деякими видами підграфів задачу пошуку ізоморфного підграфа можна розв'язати за поліноміальний час.
xsd:nonNegativeInteger
14493