A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes

DOI10.1007/978-3-319-20297-6_4zbMath1464.90014arXiv1410.7208OpenAlexW2213630799MaRDI QIDQ3194707

Alexander V. Karzanov, Maxim A. Babenko

Publication date: 20 October 2015

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

Full work available at URL: https://arxiv.org/abs/1410.7208

zbMATH Keywords

planar graphcut conditionstrongly polynomial algorithmmulti-commodity flowmultiflow(2, 3)-metric condition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Half-integral five-terminus flows
• Edge-disjoint paths in planar graphs
• Multicommodity flows in planar graphs
• A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations
• Paths and metrics in a planar graph with three or more holes. I: Metrics
• Paths and metrics in a planar graph with three or more holes. II: Paths
• Multicommodity flows in graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Half-integral flows in a planar graph with four holes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)

This page was built for publication: A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes