A fast algorithm for maximum integral two-commodity flow in planar graphs

DOI10.1016/0166-218X(93)90153-FzbMath0792.90025MaRDI QIDQ1314324

Michal Penn, Ephraim Korach

Publication date: 22 February 1994

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

zbMATH Keywords

augmented planar graphsmaximum integral two-commodity flow problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (6)

On complexity, representation and approximation of integral multicommodity flows ⋮ On the integral plane two-commodity flow problem ⋮ Disjoint paths in sparse graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs ⋮ On the complexity of the planar directed edge-disjoint paths problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the planar integer two-flow problem
• Tight integral duality gap in the Chinese postman problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• On Odd Cuts and Plane Multicommodity Flows
• On the Complexity of Timetable and Multicommodity Flow Problems
• Multi-Commodity Network Flows

This page was built for publication: A fast algorithm for maximum integral two-commodity flow in planar graphs