On the integral plane two-commodity flow problem (Q1197891)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the integral plane two-commodity flow problem |
scientific article |
Statements
On the integral plane two-commodity flow problem (English)
0 references
16 January 1993
0 references
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.
0 references
maximum integral two-commodity flow problem
0 references
augmented planar graphs
0 references
minimal increase in the weight function
0 references
