Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Graph_isomorphism_problem> ?p ?o. }
Showing items 1 to 42 of
42
with 100 items per page.
- Graph_isomorphism_problem abstract "The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and one of only two of that list whose complexity remains unresolved (the other being integer factorization). As of 2008 the best algorithm (Luks, 1983) has run time 2O(√(n log n)) for graphs with n vertices.It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level.At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.This problem is a special case of the subgraph isomorphism problem, which is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group.".
- Graph_isomorphism_problem wikiPageExternalLink PGI.
- Graph_isomorphism_problem wikiPageExternalLink spp.
- Graph_isomorphism_problem wikiPageExternalLink column86.pdf.
- Graph_isomorphism_problem wikiPageExternalLink column97.pdf.
- Graph_isomorphism_problem wikiPageExternalLink ~algorith.
- Graph_isomorphism_problem wikiPageExternalLink graph-isomorphism.shtml.
- Graph_isomorphism_problem wikiPageExternalLink CS-2006-32.pdf.
- Graph_isomorphism_problem wikiPageID "1950766".
- Graph_isomorphism_problem wikiPageRevisionID "561096064".
- Graph_isomorphism_problem hasPhotoCollection Graph_isomorphism_problem.
- Graph_isomorphism_problem subject Category:Computational_problems_in_graph_theory.
- Graph_isomorphism_problem subject Category:Graph_algorithms.
- Graph_isomorphism_problem subject Category:Morphisms.
- Graph_isomorphism_problem subject Category:Unsolved_problems_in_computer_science.
- Graph_isomorphism_problem type Abstraction100002137.
- Graph_isomorphism_problem type Act100030358.
- Graph_isomorphism_problem type Activity100407535.
- Graph_isomorphism_problem type Algorithm105847438.
- Graph_isomorphism_problem type Attribute100024264.
- Graph_isomorphism_problem type ComputationalProblemsInGraphTheory.
- Graph_isomorphism_problem type Condition113920835.
- Graph_isomorphism_problem type Difficulty114408086.
- Graph_isomorphism_problem type Event100029378.
- Graph_isomorphism_problem type GraphAlgorithms.
- Graph_isomorphism_problem type Problem114410605.
- Graph_isomorphism_problem type Procedure101023820.
- Graph_isomorphism_problem type PsychologicalFeature100023100.
- Graph_isomorphism_problem type Rule105846932.
- Graph_isomorphism_problem type State100024720.
- Graph_isomorphism_problem type UnsolvedProblemsInComputerScience.
- Graph_isomorphism_problem type YagoPermanentlyLocatedEntity.
- Graph_isomorphism_problem comment "The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and one of only two of that list whose complexity remains unresolved (the other being integer factorization). ".
- Graph_isomorphism_problem label "Graph isomorphism problem".
- Graph_isomorphism_problem label "Problème de l'isomorphisme de graphes".
- Graph_isomorphism_problem sameAs Problème_de_l'isomorphisme_de_graphes.
- Graph_isomorphism_problem sameAs m.068cxm.
- Graph_isomorphism_problem sameAs Q3738036.
- Graph_isomorphism_problem sameAs Q3738036.
- Graph_isomorphism_problem sameAs Graph_isomorphism_problem.
- Graph_isomorphism_problem wasDerivedFrom Graph_isomorphism_problem?oldid=561096064.
- Graph_isomorphism_problem isPrimaryTopicOf Graph_isomorphism_problem.