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

DOI10.1016/S0020-0190(98)00077-5MaRDI QIDQ293313zbMATH OpenOpenAlexFDO

Authors 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 pathfault tolerancelongest detourmost critical edgetransient edge failures

Mathematics Subject Classification ID

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

Recommendations

• Finding the anti-block vital edge of a shortest path between two nodes
• A faster computation of the most vital edge of a shortest path
• A simple algorithm for replacement paths problem
• Finding the most vital node of a shortest path.
• scientific article; zbMATH DE number 1796972

Cites work

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

Cited in

(14)

• Finding the Anti-block Vital Edge of a Shortest Path Between Two Nodes
• Shortest paths with shortest detours. A biobjective routing problem
• Finding the anti-block vital edge of a shortest path between two nodes
• Power-grids as complex networks: emerging investigations into robustness and stability
• The tree longest detour problem in a biconnected graph.
• Finding the most vital node of a shortest path.
• scientific article; zbMATH DE number 1796972 (Why is no real title available?)
• 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
• A faster computation of the most vital edge of a shortest path
• Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update
• Faster algorithm to find anti-risk path between two nodes of an undirected graph
• Optimal shortest path set problem in undirected graphs

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

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