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

DOI10.1016/S0020-0190(98)00077-5zbMATH Open1339.68210OpenAlexW1980494375MaRDI QIDQ293313FDOQ293313

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

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

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)

Cites Work

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

Cited In (14)

• Shortest paths with shortest detours. A biobjective routing problem
• Power-grids as complex networks: emerging investigations into robustness and stability
• Finding the anti-block vital edge of a shortest path between two nodes
• The tree longest detour problem in a biconnected graph.
• Finding the most vital node of a shortest path.
• Title not available (Why is that?)
• 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
• Finding the Anti-block Vital Edge of a Shortest Path Between Two Nodes

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)