Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
From MaRDI portal
Publication:5348455
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
- Title not available (Why is no real title available?)
- 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\log 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 min cut and 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 \log 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 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
(32)- Unit-length rectangular drawings of graphs
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- On upward-planar L-drawings of graphs
- Tiling with Squares and Packing Dominos in Polynomial Time
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Maximum contraflow evacuation planning problems on multi-network
- Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- Unit-length rectangular drawings of graphs
- scientific article; zbMATH DE number 7561502 (Why is no real title available?)
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Geometric multicut: shortest fences for separating groups of objects in the plane
- Faster shortest paths in dense distance graphs, with applications
- Improved bounds for shortest paths in dense distance graphs
- Distributed planar reachability in nearly optimal time
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Planar rectilinear drawings of outerplanar graphs in linear time
- Flows in one-crossing-minor-free graphs
- Min-Cost Flow in Unit-Capacity Planar Graphs
- Recognizing planar Laman graphs
- Radial level planarity with fixed embedding
- Minimum Cuts in Surface Graphs
- Maximum \(s\)-\(t\)-flow with \(k\) crossings in \(O(k^3 n \log n)\) time
- Flows in one-crossing-minor-free graphs
- Level-planar drawings with few slopes
- Max Flows in Planar Graphs with Vertex Capacities
- Flow in Planar Graphs with Multiple Sources and Sinks
- Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
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)
