On the integral plane two-commodity flow problem

DOI10.1016/0167-6377(92)90076-FMaRDI QIDQ1197891zbMATH OpenOpenAlexFDO

Authors Frieda Granot, Michal Penn

Publication date 16 January 1993

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(92)90076-f

zbMATH Keywords

augmented planar graphsmaximum integral two-commodity flow problemminimal increase in the weight function

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The authors consider the maximum integral two-commodity flow problem in augmented planar graphs, that is, with both source and sink edges added. An \(O(n\log n)\) simple algorithm is provided to determine the minimal increase in the weight function required to ensure that the value of a maximum plane integral two-commodity flow equals the value of the maximum plane two-commodity flow with both values equal to the original maximum two-commodity flow value.

Recommendations

• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• STACS 2004
• scientific article; zbMATH DE number 1769310
• Integer plane multiflows with a mixed number of demands

Cites work

• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Graph theory
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the planar integer two-flow problem

Cited in

(9)

• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Two commodity flows
• On the integral 4-packing of \(T\)-cuts
• Simple undirected two-commodity integral flow with a unitary demand
• scientific article; zbMATH DE number 1819779 (Why is no real title available?)
• On multicommodity flows in planar graphs
• scientific article; zbMATH DE number 1769310 (Why is no real title available?)
• STACS 2004
• Branch-and-cut for a 2-commodity flow relocation model with time constraints

This page was built for publication: On the integral plane two-commodity flow problem

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