UBC Graduate Research

Unweighted Matching in Random Graphs Nelson, Kristina

Abstract

We study the application of Edmond’s Blossom algorithm for unweighted matching on random graphs generated with the Erdos-Renyi model. Since its publication in 1965, the blossom algorithm has been the subject of great interest and research, not only in the field of matching theory but also as a linear programming problem. In the first part of this report we introduce the background and prerequisite graph theoretic definitions before describing the operation of the blossom algorithm itself. In the second part of this essay we describe our investigations around the operational running time of the algorithm and attempts to improve this value.

Item Citations and Data

License

Attribution-NonCommercial 2.5 Canada

Usage Statistics