Two graphs G, H are isomorphic if there is a relabeling of the vertices of G that produces H, and vice-versa. The graph isomorphism problem (GI) is to decide whether two given are isomorphic. In addition to its practical interest, it was identified by Karp in 1972 as having unknown complexity, is one of the few remaining natural candidates for an NP-intermediate problem, and led to the creation of the complexity class AM.
Stats
|
created |
14 years ago |
|
viewed |
77 times |
|
editors |
0 |
Top Answerers
more »
Recent Hot Answers
Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?What's the status of Babai's Graph isomorphism result?
Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?
questions on implications Babais quasi P time graph isomorphism result
For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
more »