ARC Colloquium: Seth Pettie–University of Michigan

Event Details

Dani Denton
denton at cc dot gatech dot edu


Summary Sentence: Seth Pettie presents a talk as part of the ARC Colloquium series.

Full Summary: No summary paragraph submitted.

  • Seth Pettie Seth Pettie

(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

Related Links

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, ARC Colloquium, Seth Pettie
  • Created By: Josie Giles
  • Workflow Status: Published
  • Created On: Nov 26, 2014 - 9:43am
  • Last Updated: Apr 13, 2017 - 5:21pm