ARC Colloquium: Seth Pettie–University of Michigan

(Refreshments will be served in Klaus 2222 at 2 pm)

Weighted Matching on General Graphs: Faster and Simpler

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

Seth Pettie received his Ph.D. in Computer Science from the University of Texas at Austin, in 2003.  From 2003-2006 he was an Alexander von Humboldt Postdoctoral Fellow at the Max Planck Institute for Computer Science, in Saarbruecken, Germany.  Since 2006 he has been a professor of Electrical Engineering and Computer Science at the University of Michigan, in Ann Arbor.

Seth Pettie, Assoc. Prof. in Computer Science and Engineering University of Michigan, Ann Arbor

Event Details


  • Monday, March 23, 2015
    1:00 pm - 2:00 pm