Graph isomorphism problem

By V. N. Zemlyachenko, N. M. Korneenko, R. Tyshkevich. 1985

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

1. B. Douglas
2. Jin-Yi Cai
3. Neil Immerman
4. Martin Fürer
5. Christopher Morris
6. Petra Mutzel
7. Martin Grohe
8. Jure Leskovec

Citations in the corpus

• The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “thms, such as Brendan Mackay’s ‘Nauty’ package [24]. It is also easy to solve for almost all graphs [4, 7]. However the best current GI algorithm for general graphs has an upper bound of O(e √ nlogn) [8, 32, 6]. Hence the interest in GI lies largely in its complexity status, it being one of the inte”
• An optimal lower bound on the number of variables for graph identification (1989, methodology): “The general graph isomorphism problem has been attacked by Zemlyachenko. The method is described in [5] and [ 41 ].”
• An optimal lower bound on the number of variables for graph identification (1992, methodology): “The general graph isomorphism problem has been attacked by Zemlyachenko. The method is described in [5] and [ 41 ].”