Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities

DOI10.1007/978-3-540-69733-6_57zbMath1148.90308OpenAlexW1517429022MaRDI QIDQ3511369

Weifa Liang, Xianchao Zhang, Guo-Liang Chen

Publication date: 10 July 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_57

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (1)

Maximum flow in directed planar graphs with vertex capacities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Flow equivalent trees in undirected node-edge-capacitated planar graphs
• Flow in planar graphs with vertex capacities
• A data structure for dynamic trees
• Beyond the flow decomposition barrier
• 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
• A new approach to the maximum-flow problem
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Deterministic sorting in O(nloglogn) time and linear space
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities