We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Karp–Sipser on Random Graphs with a Fixed Degree Sequence.
- Authors
BOHMAN, TOM; FRIEZE, ALAN
- Abstract
Let Δ ≥ 3 be an integer. Given a fixed z ∈ +Δ such that zΔ > 0, we consider a graph Gz drawn uniformly at random from the collection of graphs with zin vertices of degree i for i = 1,. . .,Δ. We study the performance of the Karp–Sipser algorithm when applied to Gz. If there is an index δ > 1 such that z1 = . . . = zδ−1 = 0 and δzδ,. . .,ΔzΔ is a log-concave sequence of positive reals, then with high probability the Karp–Sipser algorithm succeeds in finding a matching with n ∥ z ∥ 1/2 − o(n1−ε) edges in Gz, where ε = ε (Δ, z) is a constant.
- Subjects
RANDOM graphs; TOPOLOGICAL degree; GRAPH theory; PATHS &; cycles in graph theory; PROBABILITY theory; MATHEMATICAL sequences; MATCHING theory
- Publication
Combinatorics, Probability & Computing, 2011, Vol 20, Issue 5, p721
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548311000265