Flow in Planar Graphs with Multiple Sources and Sinks
From MaRDI portal
Publication:4857591
DOI10.1137/S0097539789162997zbMATH Open0836.68087MaRDI QIDQ4857591FDOQ4857591
Authors: Joseph (Seffi) Naor, Gary L. Miller 
Publication date: 11 April 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
- Algorithms for multicommodity flows in planar graphs
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Integer programming (90C10) Paths and cycles (05C38)
Cited In (34)
- Min-Cost Flow in Unit-Capacity Planar Graphs
- Title not available (Why is that?)
- Tiling with Squares and Packing Dominos in Polynomial Time
- INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
- Some flow-equivalent planar and non-planar graphs
- Accelerated bend minimization
- An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
- Willmore flow of planar networks
- Computing large matchings in planar graphs with fixed minimum degree
- Title not available (Why is that?)
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- Source sink flows with capacity installation in batches
- Deterministically isolating a perfect matching in bipartite planar graphs
- Space complexity of perfect matching in bounded genus bipartite graphs
- Orthogonal graph drawing with flexibility constraints
- Bipartite perfect matching is in quasi-NC
- Processor efficient parallel matching
- Fast domino tileability
- Potentials in Undirected Graphs and Planar Multiflows
- Network flow interdiction on planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Planar Maximum Matching: Towards a Parallel Algorithm
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- A topology-shape-metrics framework for ortho-radial graph drawing
- Faster shortest-path algorithms for planar graphs
- Parallel Algorithms for Zero-One Supply-Demand Problems
- Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
- Minimum Cuts in Surface Graphs
- NC algorithms for weighted planar perfect matching and related problems
- Algorithms for multicommodity flows in planar graphs
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Polymatroidal flow network models with multiple sinks
- The Lattice Structure of Flow in Planar Graphs
- Boundary-to-Boundary Flows in Planar Graphs
This page was built for publication: Flow in Planar Graphs with Multiple Sources and Sinks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4857591)
