Finding the detour-critical edge of a shortest path between two nodes

DOI10.1016/S0020-0190(98)00077-5zbMath1339.68210MaRDI QIDQ293313

Enrico Nardelli, Guido Proietti, Peter Widmayer

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000775?np=y

zbMATH Keywords

shortest path; fault tolerance; longest detour; most critical edge; transient edge failures

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Power-Grids as Complex Networks: Emerging Investigations into Robustness and Stability, Finding a contra-risk path between two nodes in undirected graphs, Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs, Finding an anti-risk path between two nodes in undirected graphs, Finding the anti-block vital edge of a shortest path between two nodes, Finding the most vital node of a shortest path., The tree longest detour problem in a biconnected graph., A faster computation of the most vital edge of a shortest path, Shortest paths with shortest detours. A biobjective routing problem, Faster algorithm to find anti-risk path between two nodes of an undirected graph, Optimal shortest path set problem in undirected graphs

Cites Work

• The k most vital arcs in the shortest path problem
• A note on finding the bridges of a graph
• Fibonacci heaps and their uses in improved network optimization algorithms