Piotr Sankowski (University of Warsaw): Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
Title: Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors. Abstract:Let G=(V,E) be a graph with degree bounds on vertices. We present the first efficient algebraic algorithm to find an f-factor. The algorithms are randomized, correct with high probability and Las Vegas. We also present three specializations of these algorithms:- For maximum weight perfect f-matching the algorithm is considerably simpler (and almost identical to its special case of ordinary weighted matching). - For the single-source shortest-path problem in undirected graphs with conservative edge weights, we present a generalization of the shortest-path tree. - For bipartite graphs, we improve the known complexity bounds for vertex capacitated max-flow and min-cost max-flow on a subclass of graphs. Joint work with Harold N. Gabow.