On the integral plane two-commodity flow problem (Q1197891): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: Publication / rank | |||
Normal rank | |||
Revision as of 02:29, 5 March 2024
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
