Department of Computer Science and Engineering

Guest Speaker: Joint CSE/Math Presentation

Button Homology Flows, Cohomology Cuts

Jeff Erikson
Dept. of Computer Science and Engineering
University of Illinois at Urbana-Champaign

Feb 5 2010 3:30PM
Math Tower

Abstract:

The maximum flow and minimum cut problems have been targets of intense algorithmic research for more than half a century. Although flows and cuts in planar graphs has been studied from the very beginning, relatively little is known about flows and cuts in even slightly more general classes of graphs. I will describe the first algorithms to compute maximum flows and minimum cuts in surface-embedded graphs in near-linear time. Except for the special case of planar graphs, the only previous time bounds for either problem follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. We exploit intimate connections between combinatorial duality of graph embeddings, Poincaré-Alexander-Lefschetz duality between homology and cohomology, and linear programming duality between flows and cuts.

The talk will be self-contained; no prior exposure to flows, cuts, or homology is assumed.

This is joint work with Erin Chambers and Amir Nayyeri. Papers describing our results can be found at http://www.cs.uiuc.edu/~jeffe/pubs/surflow.html and http://www.cs.uiuc.edu/~jeffe/pubs/surfcut.html .

Bio:

Dr. Jeff Erikson is an Associate Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He joined the CSE department in 1998 and is now also an affiliate of the Computational Science and Engineering program, a member of the steering committee for the Applied Mathematics Program, and a member of the Center for Process Simulation and Design at UIUC. A computational geometer/topologist he serves as the area chair of the CS department's algorithms group. Erikson received his Ph.D. in Computer from the University of California, Berkeley 1996 under the tutelage of Raimund Seidel. His M.S. in Information and Computer Science was granted from the University of California, Irvine, in 1992 while he studied for his B.A., in Computer Science/Mathematical Sciences at Rice University, graduating in 1987. Jeff is known for being a fan of Bruce Campbell and pancakes.

Host: Tamal Dey

OSU logo