Maximum flow in directed planar graphs with vertex capacities
From MaRDI portal
Publication:634675
DOI10.1007/S00453-010-9436-7zbMATH Open1223.05106OpenAlexW2147969479MaRDI QIDQ634675FDOQ634675
Authors: Haim Kaplan, Yahav Nussbaum 
Publication date: 16 August 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.250.7448
Recommendations
- Maximum Flow in Directed Planar Graphs with Vertex Capacities
- Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Title not available (Why is that?)
- A data structure for dynamic trees
- The Lattice Structure of Flow in Planar Graphs
- Faster shortest-path algorithms for planar graphs
- The Vertex-Disjoint Menger Problem in Planar Graphs
- Planar graphs: Theory and algorithms
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Maximum Flow in Planar Networks
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
- Flow in planar graphs with vertex capacities
- A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Flow equivalent trees in undirected node-edge-capacitated planar graphs
Cited In (22)
- Title not available (Why is that?)
- Faster shortest paths in dense distance graphs, with applications
- Lattices and maximum flow algorithms in planar graphs
- Max Flows in Planar Graphs with Vertex Capacities
- Flow trees for vertex-capacitated networks
- Depth-first search in directed planar graphs, revisited
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Recognizing planar Laman graphs
- Imposing contiguity constraints in political districting models
- Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
- Title not available (Why is that?)
- How vulnerable is an undirected planar graph with respect to max flow
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Flow equivalent trees in undirected node-edge-capacitated planar graphs
- Title not available (Why is that?)
- Maximum Flow in Directed Planar Graphs with Vertex Capacities
- Flow in planar graphs with vertex capacities
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Max flow vitality in general and \(st\)-planar graphs
- Political districting to minimize cut edges
This page was built for publication: Maximum flow in directed planar graphs with vertex capacities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634675)
