A simple algorithm for replacement paths problem

DOI10.1016/J.ENDM.2016.05.026MaRDI QIDQ327668zbMATH OpenOpenAlexFDO

Authors Anjeneya Swami Kare

Publication date 19 October 2016

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

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)

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.

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

Cites work

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

Cited in

(6)

• Near optimal algorithms for the single source replacement paths problem
• Automata, Languages and Programming
• 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

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)