Seeded graph matching via large neighborhood statistics

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

Jiaming Xu, Elchanan Mossel

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 processgraph matchinggraph isomorphismsubgraph count

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items

Correlated randomly growing graphs, Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks, Efficient random graph matching via degree profiles, Aligning random graphs with a sub-tree similarity message-passing algorithm, Exact matching of random graphs with constant correlation, Computing Autotopism Groups of Partial Latin Rectangles, Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis, Testing correlation of unlabeled random graphs, Matching recovery threshold for correlated random graphs, Unnamed Item, Unnamed Item