Show simple item record

dc.contributor.author
Erlebach, Thomas
dc.date.accessioned
2022-08-12T12:10:46Z
dc.date.available
2017-06-13T03:16:31Z
dc.date.available
2022-08-12T12:10:46Z
dc.date.issued
2001-08
dc.identifier.uri
http://hdl.handle.net/20.500.11850/145514
dc.identifier.doi
10.3929/ethz-a-004256657
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich, Computer Engineering and Networks Laboratory
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
Approximation algorithms and complexity results for path problems in trees of rings
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
TIK Report
ethz.journal.volume
109
en_US
ethz.size
19 p.
en_US
ethz.version.edition
Version 1
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.code.ddc
DDC - DDC::6 - Technology, medicine and applied sciences::621.3 - Electric engineering
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
en_US
ethz.date.deposited
2017-06-13T03:18:05Z
ethz.source
ECOL
ethz.identifier.importid
imp59366a42bdeb541252
ethz.ecolpid
eth:24442
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-15T23:49:42Z
ethz.rosetta.lastUpdated
2023-02-07T05:17:05Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Approximation%20algorithms%20and%20complexity%20results%20for%20path%20problems%20in%20trees%20of%20rings&rft.jtitle=TIK%20Report&rft.date=2001-08&rft.volume=109&rft.au=Erlebach,%20Thomas&rft.genre=report&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record