Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
From MaRDI portal
Publication:5348455
DOI10.1137/15M1042929zbMATH Open1368.05032DBLPjournals/siamcomp/BorradaileKMNW17OpenAlexW2741786970WikidataQ56341080 ScholiaQ56341080MaRDI QIDQ5348455FDOQ5348455
Philip N. Klein, Glencora Borradaile, Yahav Nussbaum, Christian Wulff-Nilsen, Shay Mozes
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
Recommendations
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
- Maximum flow in directed planar graphs with vertex capacities
- Flow in Planar Graphs with Multiple Sources and Sinks
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)
Cites Work
- Title not available (Why is that?)
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Title not available (Why is that?)
- A data structure for dynamic trees
- Beyond the flow decomposition barrier
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Max flows in O(nm) time, or better
- A new approach to the maximum-flow problem
- A survey of very large-scale neighborhood search techniques
- The Lattice Structure of Flow in Planar Graphs
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
- Title not available (Why is that?)
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Flow in Planar Graphs with Multiple Sources and Sinks
- Faster shortest-path algorithms for planar graphs
- Approximation algorithms for classification problems with pairwise relationships
- Finding small simple cycle separators for 2-connected planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths
- Multiple-source shortest paths in planar graphs
- Flows in One-Crossing-Minor-Free Graphs
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Improved algorithms for min cut and max flow in undirected planar graphs
- Title not available (Why is that?)
- Flow in planar graphs with vertex capacities
- Maximum flow in directed planar graphs with vertex capacities
- Accelerated Bend Minimization
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Title not available (Why is that?)
- Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
- Improved Submatrix Maximum Queries in Monge Matrices
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Multiple-source shortest paths in embedded graphs
- All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
Cited In (25)
- Min-Cost Flow in Unit-Capacity Planar Graphs
- Title not available (Why is that?)
- Tiling with Squares and Packing Dominos in Polynomial Time
- Faster shortest paths in dense distance graphs, with applications
- Title not available (Why is that?)
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Flow in Planar Graphs with Multiple Sources and Sinks
- Unit-length rectangular drawings of graphs
- On upward-planar L-drawings of graphs
- Unit-length rectangular drawings of graphs
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Level-planar drawings with few slopes
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Minimum Cuts in Surface Graphs
- Distributed planar reachability in nearly optimal time
- Planar rectilinear drawings of outerplanar graphs in linear time
- NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Radial Level Planarity with Fixed Embedding
- Geometric multicut: shortest fences for separating groups of objects in the plane
Uses Software
This page was built for publication: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348455)
