Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs

DOI10.1016/0166-218X(95)00111-4zbMath0865.68089MaRDI QIDQ2563924

Michal Penn, Frieda Granot

Publication date: 6 January 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

two-flow problem; vertex- and edge-capacitated

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the planar integer two-flow problem
• Disjoint paths in graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Flow in planar graphs with vertex capacities
• Integer plane multiflows with a mixed number of demands
• Graph minors. XIII: The disjoint paths problem
• On the complexity of the disjoint paths problem
• Selecting and sequencing tests in adaptive checkout processes
• Maximal Flow Through a Network
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• On Odd Cuts and Plane Multicommodity Flows
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Matching, Euler tours and the Chinese postman
• Two commodity network flows and linear programming
• Multi-Commodity Network Flows
• Faster shortest-path algorithms for planar graphs