期刊
RANDOM STRUCTURES & ALGORITHMS
卷 58, 期 3, 页码 390-429出版社
WILEY
DOI: 10.1002/rsa.20980
关键词
Karp‐ Sipser Algorithm; maximum matching; random regular graph
资金
- National Science Foundation, NSF [DMS1363136]
In a seminal paper, Karp and Sipser proposed two algorithms for finding large matchings in sparse random graphs. Their empirical results suggest that the first algorithm is superior, and this paper proves that it is indeed more effective for random k-regular graphs. The algorithm can also be adapted to find a maximum matching in O(n) time w.h.p., a significant improvement over the worst-case O(n(3/2)) time complexity.
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(n(3/2)) time for the worst-case.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据