Maximum st-flow in directed planar graphs via shortest paths

2013/05/24 by Glencora Borradaile, Anna Harutyunyan, Borradaile, Glencora +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.1305.5823

20 pages, 4 figures. Short version to be published in proceedings of IWOCA'13

arxiv created 2013/05/24 · arxiv updated 2013/05/27

Abstract

Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.

Related

• Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs
• Distributed Maximum Flow in Planar Graphs
• Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Maximum Flow in Directed Planar Graphs with Vertex Capacities