TOPICS
Search

Canonical Labeling


A canonical labeling, also called a canonical form, of a graph G is a graph G^' which is isomorphic to G and which represents the whole isomorphism class of G (Piperno 2011). The complexity class of canonical labeling is not known.

Efficient labeling methods yield an efficient tests for isomorphic graphs, as provided for example by nauty, Traces, bliss, and other software implementations.


See also

Isomorphic Graphs

Explore with Wolfram|Alpha

References

Junttila, T. and Kaski, P. "Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs." In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (Ed. D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick.) SIAM: pp. 135-149, 2007.McKay, B. "Practical Graph Isomorphism." Congr. Numer. 30, 45-87, 1981. http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.McKay, B. and Piperno, A. "Practical Graph Isomorphism, II." 8 Jan 2013. http://arxiv.org/abs/1301.1493.Piperno, A. "Search Space Contraction in Canonical Labeling of Graphs." 26 Jan 2011. http://arxiv.org/abs/0804.4881.

Cite this as:

Weisstein, Eric W. "Canonical Labeling." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CanonicalLabeling.html

Subject classifications