A primal-dual algorithm for the unconstrained fractional matching problem

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|).