[Colloquium] TTI-C Colloquium: Jeff Erickson, UIUC

[Julia MacGlashan]

When:             TODAY: Monday, October 20 @ 2:00pm

 

Where:            TTI-C Conference Room: 1427 E. 60th St, 2nd Floor

 

Who:                Jeff Erickson, University of Illinois at
Urbana-Champaign

 

Title:                 Homology Flows

 

 

I will describe the first algorithms to compute maximum flows in
surface-embedded graphs in near-linear time.  Our results generalize an O(n
log n)-time max-flow algorithm for undirected planar graphs, published by
Hassin and Johnson in 1985.  Except for this special case, the only previous
time bounds for our problem follow from algorithms for general sparse
graphs.  Our key insight is to optimize the homology class of the flow,
rather than directly optimizing the flow itself.

 

This is joint work with Erin Chambers, Amir Nayyeri, and Aparna Sundar.

 

Contact:          Benoît Hudson, TTI-C         bhudson at tti-c.org
834-2623

 

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20081020/4f827ec5/attachment.htm