"Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs"
Thursday, June 21, 2012 at 2:30 P.M.
Lubrano Conference Room (CIT 4th floor)
Large graphs are ubiquitous in many diverse fields ranging from sociology and economics to biology and engineering. Applications in numerous areas such as transportation, geographical routing, computer vision and VLSI design involve solving optimization problems on large planar graphs. The sheer growth in the number and size of available data sets drives a need to design optimization algorithms that are not merely efficient in the qualitative sense that their computational resource consumption is polynomial in the size of the input, but in the stronger quantitative sense that the amount of required resources (specifically, running time and space) is as close to linear as possible. In this thesis we study the combinatorial structural properties of directed planar graphs, and exploit these properties to devise efficient algorithms for shortest paths and maximum flow problems in such graphs. Among the results we preset are:
- A linear-space algorithm for the shortest-path problem in directed planar graphs with real (positive and negative) arc lengths that runs in near-linear time. Our algorithm is more efficient and conceptually simpler than previously known algorithms for this problem.
- Data structures for efficiently reporting exact distances in a directed planar graph (distance oracles) with significantly improved query-time to space ratio over previously known exact distance oracle.
- A near-linear time algorithm for computing a maximum flow in a directed planar graphs with multiple sources and sinks. This problem has been open for more than 20 years. No planarity exploiting algorithm for the problem was previously known. Our algorithm is significantly faster than previous algorithms for this problem.
These problems, and the tools and techniques used in solving them are inter-related.
Host: Philip Klein