Friday, May 8, 2015 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Weighted matching on general graphs: faster and simpler
Speaker: | Seth Pettie |
Affiliation: | University of Michigan |
Room: | MC 5501 |
Abstract: We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. The algorithm runs in O(mn^{1/2}log(nW)) time, where m, n, and W are the numbers of edges, vertices and maximum integer edge weight. This bound matches the fastest algorithm for bipartite graphs and comes within a log(nW) factor of the Micali-Vazirani cardinality matching algorithm. In terms of running time our algorithm is just slightly faster than the previous best (Gabow and Tarjan, 1991) by a roughly (log n)^{1/2} factor. However, it is dramatically simpler to describe and analyze.
Joint
work
with
Ran
Duan
(IIIS,
Tsinghua)
and
Hsin-Hao
Su
(University
of
Michigan). Manuscript
available
at https://arxiv.org/abs/1411.1919v2.