Upgrading edge-disjoint paths in a ring

Jácint Szabó


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-17}

Last modification: 22.11.2022. Please email your comments to Tamás Király!