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

DOI10.1016/0166-218X(93)90153-FMaRDI QIDQ1314324zbMATH OpenFDO

Authors Ephraim Korach, Michal Penn

Publication date 22 February 1994

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

Full work available at URL https://doi.org/10.1016/0166-218X(93)90153-F

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)

Recommendations

• On the integral plane two-commodity flow problem
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• Algorithms for multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

Cites work

• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Graph theory
• Multi-Commodity Network Flows
• On Odd Cuts and Plane Multicommodity Flows
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the planar integer two-flow problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Tight integral duality gap in the Chinese postman problem

Cited in

(8)

• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• Disjoint paths in sparse graphs
• Minimal multicut and maximal integer multiflow: a survey
• On the complexity of the planar directed edge-disjoint paths problem
• On complexity, representation and approximation of integral multicommodity flows
• Integral biflow maximization
• scientific article; zbMATH DE number 1769310 (Why is no real title available?)
• On the integral plane two-commodity flow problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1314324)