|
In this paper we introduce the upgrading problem for edge-disjoint paths. In the off-line upgrading problem a supply graph G and two demand graphs H_1 and H_2 are given on the same vertex set. What is the maximum size of a set F \subseteq E(H_1) \cap E(H_2) such that F has a routing in G which can be extended to a routing of H_i in G, for i=1,2? In the online upgrading problem we are given a supply graph G, a demand graph H with a routing and another demand graph H_2 such that E(H) \subseteq E(H_2). What is the maximum size of a set F \subseteq E(H) such that the restriction of the given routing to F can be extended to routing of H_2? Thus, depending on whether the graphs are directed or undirected, we have four different versions. In this paper we give full solution for the case when G is a ring and the demand graphs are stars. All four versions are NP-complete in general.
Bibtex entry:
| AUTHOR | = | {Szab{\'o}, J{\'a}cint}, |
| TITLE | = | {Upgrading edge-disjoint paths in a ring}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2005}, |
| NUMBER | = | {TR-2005-17} |