Abstract
We consider the replacement path problem for undirected graphs in case of edge failures. Given a 2-edge connected graph G(V,E), where n = |V| and m = |E|, for each edge e on the shortest s − t path of G, we are to report the shortest s − t path in G ∖ e. If d is the diameter of the graph, the proposed algorithm takes O(m + d 2) time.
For graphs where \(d = O(\sqrt{m})\), typically dense graphs, or graphs with small diameter we have a linear time solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14, 344–370 (1993)
Deo, N.: Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall (1974)
Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. FOCS, pp. 252–259 (2001)
Hershberger, J., Suri, S.: Erratum to ”Vickrey Pricing and Shortest Paths: What is an Edge Worth? In: FOCS, p. 809 (2002)
Henzinger, M.R., Klein, P., Rao, D., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3–33 (1997)
Malik, K., Mittal, A.K., Gupta, S.K.: The most vital arcs in the shortest path problem. Oper. Res. Letters 8, 223–227 (1989)
Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. Theoretical Computer Science 296, 167–177 (2003)
Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Inf. Process. Lett. 79(2), 81–85 (2001)
Tarjan, R.: Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Information Processing Letters 14(1), 30–33 (1982)
Tarjan, R.: Applications of path compression on balanced trees. J. ACM 26, 690–715 (1979)
Thorup, M.: Floats, Integers, and Single Source Shortest Paths. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 14–24. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mahadeokar, J., Saxena, S. (2012). Faster Replacement Paths Algorithm for Undirected, Positive Integer Weighted Graphs with Small Diameter. In: Arumugam, S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2012. Lecture Notes in Computer Science, vol 7643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35926-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-35926-2_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35925-5
Online ISBN: 978-3-642-35926-2
eBook Packages: Computer ScienceComputer Science (R0)