Seminar Event Detail


Theoretical Computer Science

Date:  Friday, October 02, 2015
Location:  3725 BBB (10:00 AM to 11:30 AM)

Title:  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 (MIT). Manuscript available at http://arxiv.org/abs/1411.1919v2.

Files:


Speaker:  Seth Pettie
Institution:  U-M

Event Organizer:      schoeneb

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.