𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matching Algorithms Are Fast in Sparse Random Graphs

✍ Scribed by Holger Bast; Kurt Mehlhorn; Guido Schafer; Hisao Tamaki

Publisher
Springer
Year
2005
Tongue
English
Weight
179 KB
Volume
39
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Sparse pseudo-random graphs are Hamilton
Sparse pseudo-random graphs are Hamiltonian
✍ Michael Krivelevich; Benny Sudakov πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 133 KB

## Abstract In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value Ξ» of an eigenvalue of a __d__‐regular graph __G__ on __n__ vertices satisfies and __n__ is large enough, then __G__ is Hamiltonian. We also show how our main resu

Maximum matchings in sparse random graph
Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 490 KB πŸ‘ 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3

On large matchings and cycles in sparse
On large matchings and cycles in sparse random graphs
✍ A.M Frieze πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [Β½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce

Trees in sparse random graphs
Trees in sparse random graphs
✍ W.Fernandez de la Vega πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 471 KB