We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A polynomial‐time approximation scheme for the maximal overlap of two independent Erdős–Rényi graphs.
- Authors
Ding, Jian; Du, Hang; Gong, Shuyang
- Abstract
For two independent Erdős–Rényi graphs G(n,p)$$ \mathbf{G}\left(n,p\right) $$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial‐time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by‐product, we prove that the maximal overlap is asymptotically n2α−1$$ \frac{n}{2\alpha -1} $$ for p=n−α$$ p={n}^{-\alpha } $$ with some constant α∈(1/2,1)$$ \alpha \in \left(1/2,1\right) $$.
- Subjects
POLYNOMIAL time algorithms; GREEDY algorithms; RANDOM graphs
- Publication
Random Structures & Algorithms, 2024, Vol 65, Issue 1, p220
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21212