A simple algorithm for replacement paths problem

DOI10.1016/J.ENDM.2016.05.026zbMATH Open1347.05238arXiv1511.06905OpenAlexW2963203140MaRDI QIDQ327668FDOQ327668

Authors: Anjeneya Swami Kare 

Publication date: 19 October 2016

Abstract: Let G=(V,E)(|V|=n and |E|=m) be an undirected graph with positive edge weights. Let P_{G}(s, t) be a shortest s-t path in G. Let l be the number of edges in P_{G}(s, t). The emph{Edge Replacement Path} problem is to compute a shortest s-t path in G{e}, for every edge e in P_{G}(s, t). The emph{Node Replacement Path} problem is to compute a shortest s-t path in G{v}, for every vertex v in P_{G}(s, t). In this paper we present an O(T_{SPT}(G)+m+l^2) time and O(m+l^2) space algorithm for both the problems. Where, T_{SPT}(G) is the asymptotic time to compute a single source shortest path tree in G. The proposed algorithm is simple and easy to implement.

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

Recommendations

• Automata, Languages and Programming
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
• Faster replacement paths algorithm for undirected, positive integer weighted graphs with small diameter

zbMATH Keywords

shortest pathedge replacement pathnode replacement pathreplacement pathreplacement shortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• A note on two problems in connexion with graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• The k most vital arcs in the shortest path problem
• Finding the most vital node of a shortest path.
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• A faster computation of the most vital edge of a shortest path
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Floats, Integers, and Single Source Shortest Paths
• Replacement paths via row minima of concise matrices
• Faster shortest-path algorithms for planar graphs

Cited In (6)

• Finding the detour-critical edge of a shortest path between two nodes
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Faster replacement paths algorithm for undirected, positive integer weighted graphs with small diameter
• Optimal shortest path set problem in undirected graphs
• Automata, Languages and Programming
• Near optimal algorithms for the single source replacement paths problem

This page was built for publication: A simple algorithm for replacement paths problem

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