Back to Search
Start Over
Finding maximum matchings in random regular graphs in linear expected time.
- Source :
- Random Structures & Algorithms; May2021, Vol. 58 Issue 3, p390-429, 40p
- Publication Year :
- 2021
-
Abstract
- In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results by Karp and Sipser suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random k‐regular graphs. We show that w.h.p. the first algorithm will find a matching of size n/2−O(logn) in a random k‐regular graph, k = O(1). We also show that the algorithm can be adapted to find a maximum matching in O(n) time w.h.p. This is to be compared with O(n3/2) time for the worst‐case. [ABSTRACT FROM AUTHOR]
- Subjects :
- REGULAR graphs
RANDOM graphs
SPARSE graphs
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 10429832
- Volume :
- 58
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Random Structures & Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 149170296
- Full Text :
- https://doi.org/10.1002/rsa.20980