The online replacement path problem

DOI10.1007/978-3-642-40450-4_1MaRDI QIDQ2849291zbMATH OpenOpenAlexFDO

Authors David Adjiashvili, Gianpaolo Oriolo, Marco Senatore

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.5959

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: We study a natural online variant of the replacement path problem. The extit{replacement path problem} asks to find for a given graph $G=(V,E)$, two designated vertices $s,tinV$ and a shortest $s$-$t$ path $P$ in $G$, a extit{replacement path} $P_e$ for every edge $e$ on the path $P$. The replacement path $P_e$ is simply a shortest $s$-$t$ path in the graph, which avoids the extit{failed} edge $e$. We adapt this problem to deal with the natural scenario, that the edge which failed is not known at the time of solution implementation. Instead, our problem assumes that the identity of the failed edge only becomes available when the routing mechanism tries to cross the edge. This situation is motivated by applications in distributed networks, where information about recent changes in the network is only stored locally, and fault-tolerant optimization, where an adversary tries to delay the discovery of the materialized scenario as much as possible. Consequently, we define the extit{online replacement path problem}, which asks to find a nominal $s$-$t$ path $Q$ and detours $Q_e$ for every edge on the path $Q$, such that the worst-case arrival time at the destination is minimized. Our main contribution is a label setting algorithm, which solves the problem in undirected graphs in time $O(mlogn)$ and linear space for all sources and a single destination. We also present algorithms for extensions of the model to any bounded number of failed edges.

Recommendations

• Efficient oracles and routing schemes for replacement paths
• Robust path choice in networks with failures
• A near-linear-time algorithm for computing replacement paths in planar directed graphs
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Oracles for Distances Avoiding a Failed Node or Link

Cited in

(1)

• Rerouting Flows when Links Fail

This page was built for publication: The online replacement path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849291)