A primal-dual algorithm for the unconstrained fractional matching problem

Author: 
Peer reviewed: 
Yes, item is peer reviewed.
Date created: 
2009
Abstract: 

In this thesis, we present a primal-dual algorithm for a generalization of the Maximum Matching Problem, a well known problem in graph theory. Although the proposed problem, called the unconstrained fractional matching problem, can be solved in polynomial time using established algorithms for linear programming, we provide a combinatorial algorithm with a running time complexity of O(|V|2|E|).

Language: 
English
Document type: 
Thesis
Rights: 
Copyright remains with the author. The author granted permission for the file to be printed, but not for the text to be copied and pasted.
File(s): 
Department: 
Simon Fraser University
Thesis type: 
Thesis
Statistics: