Department of Computer, Control and Management Engineering

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.