Network design problems with bounded distances via shallow-light steiner trees

DC FieldValueLanguage
dc.contributor.authorChimani, M.
dc.contributor.authorSpoerhase, J.
dc.contributor.editorMayr, E.W.
dc.contributor.editorOllinger, N.
dc.date.accessioned2021-12-23T16:32:25Z-
dc.date.available2021-12-23T16:32:25Z-
dc.date.issued2015
dc.identifier.isbn9783939897781
dc.identifier.issn18688969
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17345-
dc.descriptionConference of 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 ; Conference Date: 4 March 2015 Through 7 March 2015; Conference Code:111047
dc.description.abstractIn a directed graph G with non-correlated edge lengths and costs, the network design problem with bounded distances asks for a cost-minimal spanning subgraph subject to a length bound for all node pairs. We give a bi-criteria (2 ε,O(n0.5+ε))-approximation for this problem. This improves on the currently best known linear approximation bound, at the cost of violating the distance bound by a factor of at most 2 ε. In the course of proving this result, the related problem of directed shallow-light Steiner trees arises as a subproblem. In the context of directed graphs, approximations to this problem have been elusive. We present the first non-trivial result by proposing a (1+ε,O(|R|ε))-approximation, where R is the set of terminals. Finally, we show how to apply our results to obtain an (α ε,O(n0.5+ε))-approximation for light-weight directed α-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and ε and are polynomial in n for any fixed ε > 0. © 2015 LIPICS.
dc.language.isoen
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.relation.ispartofLeibniz International Proceedings in Informatics, LIPIcs
dc.subjectApproximation algorithm
dc.subjectApproximation algorithms
dc.subjectDirected graphs, Distance bound
dc.subjectLight weight
dc.subjectLinear approximations
dc.subjectNetwork design
dc.subjectNetwork design problems
dc.subjectShallow-light spanning trees
dc.subjectSpanners
dc.subjectSpanning tree
dc.subjectSteiner trees, Trees (mathematics)
dc.titleNetwork design problems with bounded distances via shallow-light steiner trees
dc.typeconference paper
dc.identifier.doi10.4230/LIPIcs.STACS.2015.238
dc.identifier.scopus2-s2.0-84923910486
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84923910486&doi=10.4230%2fLIPIcs.STACS.2015.238&partnerID=40&md5=f442a6a9669db45da2193dc26ee8cf31
dc.description.volume30
dc.description.startpage238
dc.description.endpage248
dcterms.isPartOf.abbreviationLeibniz Int. Proc. Informatics, LIPIcs
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

4
Last Week
0
Last month
0
checked on May 27, 2024

Google ScholarTM

Check

Altmetric