Campus Event Calendar
Event Entry
What and Who
Flows in 1-crossing-minor-free graphs
Erin Wolf Chambers
Saint Louis University
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 4 July 2011
14:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk, we examine the maximum flow problem in directed
H-minor-free graphs, where H can be drawn in the plane with one
crossing, giving an O(n log n) algorithm (assuming a certain
decomposition of the graph is given as input). This algorithm is part
of a body of work whose goal is near-linear time algorithms to compute
maximum flows and minimum cuts in generalizations of planar graphs,
such as minor free graphs and topological graphs. Currently known
algorithms and open problems in this area will both be surveyed.
Contact
Michael Sagraloff
--email hidden
passcode not visible
logged in users only
Michael Sagraloff, 06/29/2011 15:52 -- Created document.