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
• 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
• 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

This page was built for publication: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time