Carnegie Mellon University
file.pdf (351.41 kB)

Karp-Sipser on random graphs with a fixed degree sequence

Download (351.41 kB)
journal contribution
posted on 2011-05-16, 00:00 authored by Tom Bohman, Alan FriezeAlan Frieze

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 nz1/2 − o(n1−ε) edges in Gz, where ε = ε (Δ, z) is a constant.


Publisher Statement

© Cambridge University Press



Usage metrics