On the integral plane two-commodity flow problem (Q1197891)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 92007
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the integral plane two-commodity flow problem |
scientific article; zbMATH DE number 92007 |
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
0.9217036962509156
0 references
0.8469497561454773
0 references
0.8256706595420837
0 references
