The complexity of McKay's canonical labeling algorithm

By Takunari Miyazaki. 1995

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. Tommi A. Junttila
2. Konstantin Kutzkov
3. Petteri Kaski
4. Mohamed Ahmed
5. Mathias Niepert
6. B. Douglas

Citations in the corpus

• Learning Convolutional Neural Networks for Graphs (2016, background): “We have The term exp( k ) comes from the worst-case complexity of the graph canonicalization algo-rithm N AUTY on a k node graph (Miyazaki, 1997).”
• The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “Basic properties of these graphs are discussed in detail in [10] (also see [27] and [28] for additional details).”
• Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, methodology): “Miyazaki construction Miyazaki’s construction [32] is based on the Cai–Fürer–Immerman construction applied to a specific 3-regular multigraph.”