Multiple-source multiple-sink maximum flow in planar graphs

2010/12/21 by Yahav Nussbaum, Nussbaum, Yahav
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2

paper · pdf · doi:10.48550/arxiv.1012.4767

openalex publication_date 2010/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we show an O(n^(3/2) log² n) time algorithm for finding a maximum flow in a planar graph with multiple sources and multiple sinks. This is the fastest algorithm whose running time depends only on the number of vertices in the graph. For general (non-planar) graphs the multiple-source multiple-sink version of the maximum flow problem is as difficult as the standard single-source single-sink version. However, the standard reduction does not preserve the planarity of the graph, and it is not known how to generalize existing maximum flow algorithms for planar graphs to the multiple-source multiple-sink maximum flow problem.

Citations

• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in O(n^1.5 log n) Time
• Multiple source, single sink maximum flow in a planar graph
• Efficient Planarity Testing

Related

• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Multiple source, single sink maximum flow in a planar graph
• 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 O(n^1.5 log n) Time
• Multiple-source single-sink maximum flow in directed planar graphs in O(n^1.5 log n) time