Flow in planar graphs with vertex capacities

DOI10.1007/BF01240733zbMath0794.68114MaRDI QIDQ1317474

Samir Khuller, Joseph (Seffi) Naor

Publication date: 1994

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

planar graphsnetwork flowvertex capacitiescirculation problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities, Maximum flow in directed planar graphs with vertex capacities, Network flow interdiction on planar graphs, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding small simple cycle separators for 2-connected planar graphs
• Multi-terminal maximum flows in node-capacitated networks
• The maximum flow problem is log space complete for P
• Planar graphs: Theory and algorithms
• Fast and efficient solution of path algebra problems
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• Maximal Flow Through a Network
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• Configuration of VLSI Arrays in the Presence of Defects
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Multi-Terminal Network Flows
• Maximum Flow in Planar Networks
• Generalized Nested Dissection
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time