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.
 Abstract Let P G (r,s) denote a shortest path between two nodes r and s in an undirected graph G=(V,E) such that |V|=n and |E|=m and with a positive real length w(e) associated with any e∈E . In this paper we focus on the problem of finding an edge e ∗ ∈P G (r,s) whose removal is such that the length of P G−e ∗ (r,s) is maximum, where G−e ∗ =(V,E⧹ e ∗ ) . Such an edge is known as the most vital edge of the path P G (r,s) . We will show that this problem can be solved in O (m·α(m,n)) time, where α is the functional inverse of the Ackermann function, thus improving on the previous O (m+n log n) time bound. In an undirected, 2-node connected graph G= (V,E) with positive real edge lengths, the distance between anyt wo nodes r and s is the length of a shortest path between r and s in G. The removal of a node and its incident edges from G may increase the distance from r to s. A most vital node of a given shortest path from rto s is a node (other than r and s) whose removal from G results in the largest increase of the distance from r to s. In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiencythe most. In this paper, we show that this problem can be solved in O(m+ nlog n) time and O(m) space, where mand n denote the number of edges and the number of nodes in G. Abstract Let P G ( r , s ) denote a shortest path between two nodes r and s in an undirected graph G with nonnegative edge weights. A detour at a node u ϵ P G ( r , s ) = 〈 r ,…, u , v ,…, s 〉 is defined as a shortest path P G − e ( u , s ) from u to s which does not make use of ( u , v ). In this paper we focus on the problem of finding an edge e = ( u , v ) ϵ P G ( r , s ) whose removal produces a detour at node u such that the length of P G − e ( u , s ) minus the length of P G ( u , s ) is maximum. We call such an edge a detour-critical edge . We will show that this problem can be solved in O( m + n log n ) time, where n and m denote the number of nodes and edges in the graph, respectively. The k most vital arcs in a network are those whose removal from the network results in the greatest increase in the shortest distance between two specified nodes. An exact algorithm is proposed to determine the k most vital arcs. Furthermore, an algorithm of time complexity equal to that of Dijkstra's algorithm for the shortest path problem is developed to solve the single most vital arc problem.