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)

zbMATH Keywords

random graphsgraph isomorphism problemcanonical labelings

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3667973 (Why is no real title available?)
• scientific article; zbMATH DE number 125466 (Why is no real title available?)
• Asymptotic normality of subcubes in random subgraphs of the \(n\)-cube
• Connectivity properties of random subgraphs of the cube
• 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

(6)

• Improved random graph isomorphism
• McKay's canonical graph labeling algorithm
• Generic case complexity of the graph isomorphism problem
• Engineering an efficient canonical labeling tool for large and sparse graphs
• scientific article; zbMATH DE number 3999309 (Why is no real title available?)
• 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)