Effcient oracles and routing schemes for replacement paths
dc.contributor.author
Bilò, Davide
dc.contributor.author
Choudhary, Keerti
dc.contributor.author
Gualà, Luciano
dc.contributor.author
Leucci, Stefano
dc.contributor.author
Parter, Merav
dc.contributor.author
Proietti, Guido
dc.contributor.editor
Niedermeier, Rolf
dc.contributor.editor
Vallée, Brigitte
dc.date.accessioned
2019-06-28T16:59:44Z
dc.date.available
2018-04-06T05:16:47Z
dc.date.available
2018-04-06T10:14:19Z
dc.date.available
2019-06-28T16:59:44Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-062-0
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.STACS.2018.13
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/255667
dc.identifier.doi
10.3929/ethz-b-000255667
dc.description.abstract
Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results:
(1) DSO: For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings.
(2) FTP: We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors).
(3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Fault Tolerant
en_US
dc.subject
Shortest Path
en_US
dc.subject
Oracle
en_US
dc.subject
Routing
en_US
dc.title
Effcient oracles and routing schemes for replacement paths
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
96
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
13
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
en_US
ethz.event.location
Caen, France
en_US
ethz.event.date
February 28 - March 3, 2018
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
ethz.date.deposited
2018-04-06T05:16:57Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-04-06T10:14:21Z
ethz.rosetta.lastUpdated
2024-02-02T08:25:20Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Effcient%20oracles%20and%20routing%20schemes%20for%20replacement%20paths&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2018&rft.volume=96&rft.spage=13&rft.issn=1868-8969&rft.au=Bil%C3%B2,%20Davide&Choudhary,%20Keerti&Gual%C3%A0,%20Luciano&Leucci,%20Stefano&Parter,%20Merav&rft.isbn=978-3-95977-062-0&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.STACS.2018.13&rft.btitle=35th%20Symposium%20on%20Theoretical%20Aspects%20of%20Computer%20Science%20(STACS%202018)
Files in this item
Publication type
-
Conference Paper [34975]