| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141503 | Discrete Optimization | 2011 | 9 Pages |
In this paper, we introduce the upgrading problem of edge-disjoint paths. In the off-line upgrading problem, a supply graph GG with integer capacities and two demand graphs H1H1 and H2H2 with unit demands are given on the same vertex set. Our task is to determine the maximum size of a set F⊆E(H1)∩E(H2)F⊆E(H1)∩E(H2) such that FF has an integer routing in GG which can be extended both to an integer routing of H1H1 and to an integer routing of H2H2. In the online upgrading problem, we are given a supply graph GG with integer capacities, a demand graph HH with an integer routing, and another demand graph H2H2 with unit demands such that E(H)⊆E(H2)E(H)⊆E(H2). Our task is to determine the maximum size of a set F⊆E(H)F⊆E(H) such that the restriction of the given routing to FF can be extended to an integer routing of H2H2. Thus, depending on whether the graphs are directed or undirected, we have four different versions. We give algorithmic proofs of minimax formulas for the case when GG is a ring and the demand graphs are stars with the same center. All four versions are NP-complete for general graphs.
