Title: New and Simple Algorithms for Stable Flow Problems
|Affiliation:||University of Waterloo|
In the previous reading group talk we defined stable flows and saw that they always exist by a reduction to the stable allocation problem. This talk, which is based on the paper of Cseh and Matuschke by the same title, will present a novel augmenting path algorithm for computing stable flows. We will extend these results to stable flows where each edge has a lower and upper bound on the flow that passes on that edge. This extension will yield a simple polynomial time algorithm for stable mathings with forced and forbidden edges.
200 University Avenue West
Waterloo, ON N2L 3G1