Some problems related to the Karp-Sipser algorithm on random graphs

Thesis

We study certain questions related to the performance of the Karp-Sipser algorithm on the sparse Erdős-Rényi random graph.

The Karp-Sipser algorithm, introduced by Karp and Sipser [34] is a greedy algorithm which aims to obtain a near-maximum matching on a given graph. The algorithm evolves through a sequence of steps. In each step, it picks an edge according to a certain rule, adds it to the matching and removes it from the remaining graph. The algorithm stops when the reminin...

Expand abstract

Authors: Kreacic, E

• DOI: 10.5287/ora-zbz1j8xqw
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Keywords: Erdős-Rényi model; maximum matching number; Karp-Sipser algorithm; Markov chain; random graph; central limit theorem; matchings; maximum matching; fluid limit method; exploration process; diffusion limit; configuration model
• Subjects: Random graphs