Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 1849127 (Why is no real title available?)
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- scientific article; zbMATH DE number 6297748 (Why is no real title available?)
- A data structure for dynamic trees
- A fully dynamic approximation scheme for shortest paths in planar graphs
- A new approach to the maximum-flow problem
- A survey of very large-scale neighborhood search techniques
- Accelerated bend minimization
- All-pairs minimum cuts in near-linear time for surface-embedded graphs
- An O(n n) algorithm for maximum st-flow in a directed planar graph
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
- Beyond the flow decomposition barrier
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Faster shortest-path algorithms for planar graphs
- Finding small simple cycle separators for 2-connected planar graphs
- Flow in Planar Graphs with Multiple Sources and Sinks
- Flow in planar graphs with vertex capacities
- Flows in one-crossing-minor-free graphs
- Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
- Improved submatrix maximum queries in Monge matrices
- Max flows in O(nm) time, or better
- Maximum s-t-flow with k crossings in O(k^3 n n) time
- Maximum flow in directed planar graphs with vertex capacities
- Multiple-source shortest paths in embedded graphs
- Multiple-source shortest paths in planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
- Submatrix maximum queries in Monge matrices are equivalent to predecessor search
- The Lattice Structure of Flow in Planar Graphs
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
Cited in
(33)- Maximum s-t-flow with k crossings in O(k^3 n n) time
- Min-Cost Flow in Unit-Capacity Planar Graphs
- scientific article; zbMATH DE number 7561502 (Why is no real title available?)
- Faster shortest paths in dense distance graphs, with applications
- Tiling with Squares and Packing Dominos in Polynomial Time
- Max Flows in Planar Graphs with Vertex Capacities
- 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
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- Maximum contraflow evacuation planning problems on multi-network
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
- Recognizing planar Laman graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Radial level planarity with fixed embedding
- Flow in Planar Graphs with Multiple Sources and Sinks
- Unit-length rectangular drawings of graphs
- Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
- 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
- Improved bounds for shortest paths in dense distance graphs
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Level-planar drawings with few slopes
- Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Minimum Cuts in Surface Graphs
- Distributed planar reachability in nearly optimal time
- Planar rectilinear drawings of outerplanar graphs in linear time
- Flows in one-crossing-minor-free graphs
- An O(n n) algorithm for maximum st-flow in a directed planar graph
- Flows in one-crossing-minor-free graphs
- Geometric multicut: shortest fences for separating groups of objects in the plane
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)
