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

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

Guido Proietti, Enrico Nardelli, 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 pathfault tolerancelongest detourmost critical edgetransient edge failures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

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

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

This page was built for publication: Finding the detour-critical edge of a shortest path between two nodes