Paper Info
Title
Karp-sipser on random graphs with a fixed degree sequence
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.
Year
DOI
Venue
2011
10.1017/S0963548311000265
Combinatorics, Probability & Computing
Keywords
Field
DocType
random graph,zin vertex,karp-sipser algorithm,fixed degree sequence,high probability,degree i,log-concave sequence,positive real
Integer,Discrete mathematics,Graph,Combinatorics,Random graph,Vertex (geometry),Degree (graph theory),Mathematics
Journal
Volume
Issue
ISSN
20
5
0963-5483
Citations 
PageRank 
References 
6
0.60
14
Authors
2
Name
Order
Citations
PageRank
Tom Bohman125033.01
Alan M. Frieze24837787.00