Graph isomorphism problem


Topic history | v1 (current) | created by janarez

Details

Graph isomorphism problem

| 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

authors

This topic has no history of related authors.