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 (11)

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

This page was built for publication: Seeded graph matching via large neighborhood statistics