On the integral plane two-commodity flow problem (Q1197891): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q5422499 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the Complexity of Timetable and Multicommodity Flow Problems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A fast algorithm for maximum integral two-commodity flow in planar graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the planar integer two-flow problem / rank | |||
Normal rank | |||
Revision as of 14:33, 16 May 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
