Graph isomorphism problem
Topic history | v1 (current) | created by janarez
Details
Graph isomorphism problem
see v1 | created by janarez | Add resource "The Weisfeiler-Lehman Isomorphism Test"
- Title
- Graph isomorphism problem
- Description
- The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. 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.
- Link
- https://en.wikipedia.org/?curid=1950766
resources
treated in The Weisfeiler-Lehman Isomorphism Test
authors
This topic has no history of related authors.