Piotr Sankowski (University of Warsaw): Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors

Data dell'evento: 
Mercoledì, 6 Novembre, 2013 - 12:00
DIAG - Via Ariosto 25, Aula Magna
Piotr Sankowski

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.   

Stefano Leonardi