Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
From MaRDI portal
Publication:5348455
DOI10.1137/15M1042929zbMath1368.05032WikidataQ56341080 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)
05C10: Planar graphs; geometric and topological aspects of graph theory
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
05C21: Flows in graphs
Related Items
Uses Software
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
- Shortest paths in directed planar graphs with negative lengths
- Flows in One-Crossing-Minor-Free 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
