Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 454.05038
Autor: Babai, Laszlo; Erdös, Paul; Selkow, Stanley M.
Title: Random graph isomorphism. (In English)
Source: SIAM J. Comput. 9, 628-635 (1980).
Review: A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but O(2\binom n2) of the 2\binom n2) graphs on n vertices). Hence, for almost all graphs X, and graph Y can be easily tested for isomorphism to X by an extremly naive linear time algorithm. This result is based on the following: In almost all graphs on n vertices, the largest n0,15 degrees are distinct. In fact, they are pairwise at least n0,03 apart.
Classif.: * 05C35 Extremal problems (graph theory)
68Q20 Nonnumerical algorithms
Keywords: isomorphism testing; canonical labeling; random graph; linear time; degree sequence of a graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag