Multiple source, single sink maximum flow in a planar graph

2010/08/29 by Glencora Borradaile, Borradaile, Glencora, Christian Wulff‐Nilsen +1 · 1 citation
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) #FOS: Computer and information sciences #G.2.2

paper · pdf · doi:10.48550/arxiv.1008.4966

openalex publication_date 2010/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an O(n^1.5log n) time algorithm for finding the maximum flow in a directed planar graph with multiple sources and a single sink. The techniques generalize to a subquadratic time algorithm for bounded genus graphs.

Cited by

• Multiple-source multiple-sink maximum flow in planar graphs

Related

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