Fast canonical labeling of random subgraphs
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.
- Asymptotic normality of subcubes in random subgraphs of the \(n\)-cube
- Connectivity properties of random subgraphs of the cube
- scientific article; zbMATH DE number 3667973 (Why is no real title available?)
- scientific article; zbMATH DE number 125466 (Why is no real title available?)
- Improved random graph isomorphism
- On the diameter and radius of randon subgraphs of the cube
- Random Graph Isomorphism
- Random graphs.
- The Evolution of Random Subgraphs of the Cube
- The Giant Component in a Random Subgraph of a Given Graph
- The Spectral Gap of a Random Subgraph of a Graph
- Generic case complexity of the graph isomorphism problem
- McKay's canonical graph labeling algorithm
- Random Graph Isomorphism
- scientific article; zbMATH DE number 3999309 (Why is no real title available?)
- scientific article; zbMATH DE number 867694 (Why is no real title available?)
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Improved random graph isomorphism
This page was built for publication: Fast canonical labeling of random subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2375981)
