User:Nywillb/Graph isomorphism problem
 | This is not a Wikipedia article: It is one user's draft page that he or she is 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[change | change source]
- ↑ Schöning, Uwe (1987). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37: 312–323.
Other websites[change | change source]
[[Category:Pages created with the Article Wizard from 2019]]