Canonical labelling of graphs in linear average time

1 October 1979

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 39-46
https://doi.org/10.1109/sfcs.1979.8

Abstract

Canonical labelling of graphs (CL, for short) can be used, e.g., to test isomorphism. We prove that a simple vertex classification procedure results after only two refinement steps in a CL of random graphs with probability 1 - exp(-cn). With a slight modification we obtain a linear time CL algorithm with only exp(-cn log n/log log n) probability of failure. An additional depth-first search yields a CL of all graphs in linear average time.

Keywords

This publication has 6 references indexed in Scilit:

Random Graph Isomorphism
SIAM Journal on Computing, 1980
On the Complexity of Canonical Labeling of Strongly Regular Graphs
SIAM Journal on Computing, 1980
Probabilistic analysis of a canonical numbering algorithm for graphs
Proceedings of Symposia in Pure Mathematics, 1979
A new algorithm for digraph isomorphism
BIT Numerical Mathematics, 1977
A Fast Monte-Carlo Test for Primality
SIAM Journal on Computing, 1977
Asymmetric graphs
Acta Mathematica Hungarica, 1963