Fast canonical labeling of random subgraphs (Q2375981)

This paper is related to the isomorphism problem between two given graphs. In particular, it has to do with the canonical labeling of graphs. It introduces the notion of a CL-rej algorithm - this is an algorithm which given a graph that belongs to an admissible class of graphs, it outputs a rearrangement of its vertices with the property that for any two isomorphic graphs that belong to that class the application of the corresponding rearrangement superimposes their edge sets. The author gives such an algorithm which operates in linear time (in the size of the input) and a random graph with edge probability \(\omega (\ln^4 n /( n \ln \ln n ))\) is admissible for this algorithm with probability that tends to 1 faster than any polynomial.