Maximum flow in directed planar graphs with vertex capacities

DOI10.1007/S00453-010-9436-7zbMath1223.05106OpenAlexW2147969479MaRDI QIDQ634675

Yahav Nussbaum, Haim Kaplan

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

zbMATH Keywords

planar graphmaximum flowvertex-disjoint pathsacyclic flowvertex capacities

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Related Items (6)

Imposing Contiguity Constraints in Political Districting Models ⋮ Depth-first search in directed planar graphs, revisited ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Unnamed Item ⋮ Political districting to minimize cut edges

Cites Work

• Unnamed Item
• Unnamed Item
• Flow equivalent trees in undirected node-edge-capacitated planar graphs
• Planar graphs: Theory and algorithms
• Flow in planar graphs with vertex capacities
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
• A data structure for dynamic trees
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• The Lattice Structure of Flow in Planar Graphs
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• Maximum Flow in Planar Networks
• The Vertex-Disjoint Menger Problem in Planar Graphs
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Maximum flow in directed planar graphs with vertex capacities