Seeded graph matching via large neighborhood statistics

DOI10.1002/rsa.20934zbMath1453.05073arXiv1807.10262MaRDI QIDQ5136925

Elchanan Mossel, Jiaming Xu

Publication date: 30 November 2020

Published in: Random Structures & Algorithms, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.10262

zbMATH Keywords

branching process; graph matching; graph isomorphism; subgraph count

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C42: Density (toughness, etc.)