Approximation algorithms and complexity results for path problems in trees of rings
Open access
Author
Date
2001-08Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
A tree of rings is a network that is obtained by interconnecting rings in a tree structure such that any two rings share at most one node. A connection request (call) in a tree of rings is given by its two endpoints and, in the case of prespecified paths, a path connecting these two endpoints. We study undirected trees of rings as well as bidirected trees of rings. In both cases, we show that the path packing problem (assigning paths to calls so as to minimize the maximum load) can be solved in polynomial time, that the path coloring problem with prespecified paths can be approximated within a constant factor, and that the maximum (weight) edge-disjoint paths problem is APX-hard and can be approximated within a constant factor (no matter whether the paths are prespecified or can be determined by the algorithms). We also consider fault-tolerance in trees of rings: If a set of calls has been established along edge-disjoint paths and if an arbitrary link fails in every ring of the tree of rings, we show that at least one third of the calls can be recovered if rerouting is allowed. Furthermore, computing the optimal number of calls that can be recovered is shown to be polynomial in undirected trees of rings and APX-hard in bidirected trees of rings. Show more
Permanent link
https://doi.org/10.3929/ethz-a-004256657Publication status
publishedJournal / series
TIK ReportVolume
Publisher
ETH Zurich, Computer Engineering and Networks LaboratoryEdition / version
Version 1Organisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
More
Show all metadata
ETH Bibliography
yes
Altmetrics