Fast canonical labeling of random subgraphs

DOI10.1134/S1064562413020154MaRDI QIDQ2375981zbMATH OpenFDO

Authors M. I. Tikhomirov

Publication date 25 June 2013

Published in Doklady Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S1064562413020154

zbMATH Keywords

canonical labelingsgraph isomorphism problemrandom graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Improved random graph isomorphism
• Random Graph Isomorphism
• McKay's canonical graph labeling algorithm
• scientific article; zbMATH DE number 3841910
• The random selection of unlabeled graphs

Cites work

• 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

Cited in

(7)

• 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)