We study a natural online variant of the replacement path problem. The asks to find for a given graph @math , two designated vertices @math and a shortest @math - @math path @math in @math , a @math for every edge @math on the path @math . The replacement path @math is simply a shortest @math - @math path in the graph, which avoids the edge @math . 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 , which asks to find a nominal @math - @math path @math and detours @math for every edge on the path @math , 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 @math 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.
Another problem which bears resemblance to ORP is the (SSPR), studied by Andreatta and Romeo @cite_18 . This problem can be seen as the stochastic analogue of ORP.
@cite_18
2057742448
This paper considers Stochastic Shortest Path (SSP) problems in probabilistic networks. A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretations and applications. We have chosen to look at the case where detours from the original path must be taken whenever the “first-choice” arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochastic programming to this problem and the proof that the computational complexity of a particular SSP problem is polynomial.