Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

DOI10.1137/15M1042929zbMath1368.05032OpenAlexW2741786970WikidataQ56341080 ScholiaQ56341080MaRDI QIDQ5348455

Glencora Borradaile, Yahav Nussbaum, Christian Wulff-Nilsen, Shay Mozes, Philip N. Klein

Publication date: 16 August 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1042929

zbMATH Keywords

planar graphsmaximum flow

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Related Items

Planar rectilinear drawings of outerplanar graphs in linear time, Minimum Cuts in Surface Graphs, Tiling with Squares and Packing Dominos in Polynomial Time, Unit-length rectangular drawings of graphs, Unnamed Item, Faster shortest paths in dense distance graphs, with applications, Unnamed Item, Geometric multicut: shortest fences for separating groups of objects in the plane, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Unnamed Item, Unnamed Item, Level-planar drawings with few slopes, Min-Cost Flow in Unit-Capacity Planar Graphs, Single-source shortest paths and strong connectivity in dynamic planar graphs, Radial Level Planarity with Fixed Embedding, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time, Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

Uses Software

• MAXFLOW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum flow in directed planar graphs with vertex capacities
• A survey of very large-scale neighborhood search techniques
• Finding small simple cycle separators for 2-connected planar graphs
• A fully dynamic approximation scheme for shortest paths in planar graphs
• Flow in planar graphs with vertex capacities
• A data structure for dynamic trees
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Multiple-Source Shortest Paths in Embedded Graphs
• Shortest paths in directed planar graphs with negative lengths
• Flows in One-Crossing-Minor-Free Graphs
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
• The Lattice Structure of Flow in Planar Graphs
• Beyond the flow decomposition barrier
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
• Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Approximation algorithms for classification problems with pairwise relationships
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• A new approach to the maximum-flow problem
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Flow in Planar Graphs with Multiple Sources and Sinks
• Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
• Improved Submatrix Maximum Queries in Monge Matrices
• Improved algorithms for min cut and max flow in undirected planar graphs
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Max flows in O(nm) time, or better
• Accelerated Bend Minimization
• Faster shortest-path algorithms for planar graphs