Home » Node » 6757

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

Speaker: 
Piotr Sankowski
Data dell'evento: 
Mercoledì, 6 November, 2013 - 12:00
Luogo: 
DIAG - Via Ariosto 25, Aula Magna
Contatto: 
Stefano Leonardi
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.     
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma