Open Collections

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 Metadata

Title
Unweighted Matching in Random Graphs
Creator
Nelson, Kristina
Date Issued
2014-12-17
Description
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.
Subject
Algorithms; Blossoming (Mathematics)
Genre
Report
Type
Text
Language
eng
Series
University of British Columbia. MATH 448
Date Available
2015-10-24
Provider
Vancouver : University of British Columbia Library
Rights
Attribution-NonCommercial 2.5 Canada
DOI
10.14288/1.0220735
URI
http://hdl.handle.net/2429/54897
Affiliation
Mathematics, Department of; Science, Faculty of
Campus
UBCV
Peer Review Status
Unreviewed
Scholarly Level
Graduate
Rights URI
http://creativecommons.org/licenses/by-nc/2.5/ca/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial 2.5 Canada