User:Nywillb/Graph isomorphism problem

This is not a Wikipedia article: It is one user's draft page that they are working on. It may be incomplete and/or unreliable.
This page was last edited by Nywillb (talk | contribs) 5 years ago.

The graph isomorphism problem is the problem in computer science and graph theory of being able to tell if two graphs are the same but with different names (isomorphic).

We do not currently know how to solve the problem in less than polynomial time, meaning that in the worst case, an algorithm to determine if the two graphs are isomorphic would take a polynomial with the number of vertices and edges as a variable steps. We also do not know if the problem is NP-complete.^[1]

References

↑ Schöning, Uwe (1987). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37: 312–323.

Other websites

example.com

[[Category:Pages created with the Article Wizard from 2019]]

[1] Schöning, Uwe (1987). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37: 312–323.

[1]