کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430560 | 688041 | 2013 | 9 صفحه PDF | دانلود رایگان |
In this paper, we study the following replacement paths problem for undirected graphs in case of edge or node failures.1.In the edge failure problem, for each edge e on a shortest s–ts–t path in G , we are required to find a shortest s–ts–t path in G−eG−e.2.In the node failure problem, for each node v on a shortest s–ts–t path, we need to report a shortest s–ts–t path in G−vG−v.3.In the detour critical problem, for each edge (u,v)(u,v) on a shortest s–ts–t path, we have to report a shortest u–tu–t path in G−(u,v)G−(u,v). If m is the number of edges and d is the distance between s and t , which in turn will be bounded by the diameter of the graph, the proposed algorithm for all these problems takes O(m+d2)O(m+d2) time, for graphs with integer weights (on the RAM model) and on planar graphs. For typically dense graphs, or graphs with small diameter (formally, when d=O(m)), the algorithms take linear time.
Journal: Journal of Discrete Algorithms - Volume 23, November 2013, Pages 54–62