Improved random graph isomorphism

DOI10.1016/j.jda.2007.01.002zbMath1157.05046OpenAlexW2052728310MaRDI QIDQ954962

Tomek Czajka, Gopal Pandurangan

Publication date: 18 November 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.01.002

zbMATH Keywords

random graphsgraph isomorphismcanonical labelingmartingale analysis

Mathematics Subject Classification ID

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

Related Items (11)

Fast canonical labeling of random subgraphs ⋮ Efficient random graph matching via degree profiles ⋮ Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism ⋮ Exact matching of random graphs with constant correlation ⋮ Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis ⋮ Isomorphism for random \(k\)-uniform hypergraphs ⋮ Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs ⋮ Shotgun assembly of Erdős-Rényi random graphs ⋮ Novel techniques to speed up the computation of the automorphism group of a graph ⋮ Random Models and Analyses for Chemical Graphs ⋮ On the Rigidity of Sparse Random Graphs

Cites Work

• Random Graph Isomorphism
• Distinguishing Vertices of Random Graphs
• Probability and Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved random graph isomorphism