A faster computation of the most vital edge of a shortest path

DOI10.1016/S0020-0190(00)00175-7zbMath1013.68134OpenAlexW1978228527WikidataQ127613489 ScholiaQ127613489MaRDI QIDQ1603442

Guido Proietti, Enrico Nardelli, Peter Widmayer

Publication date: 14 July 2002

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00175-7

zbMATH Keywords

shortest pathgraph algorithmsreplacement shortest pathmost vital edgetransient failure

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Finding a contra-risk path between two nodes in undirected graphs, A simple algorithm for replacement paths problem, Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths, Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs, Finding the most vital node of a shortest path., An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, Exact and approximate truthful mechanisms for the shortest paths tree problem, An improved algorithm for computing all the best swap edges of a tree spanner, The swap edges of a multiple-sources routing tree, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, Faster algorithm to find anti-risk path between two nodes of an undirected graph, Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm, Finding an anti-risk path between two nodes in undirected graphs, Finding the anti-block vital edge of a shortest path between two nodes, Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles, A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners, Incremental distance products via faulty shortest paths, Unnamed Item, Optimal shortest path set problem in undirected graphs

Cites Work

• Finding the detour-critical edge of a shortest path between two nodes
• The k most vital arcs in the shortest path problem
• A note on finding the bridges of a graph
• Applications of Path Compression on Balanced Trees
• Efficiency of a Good But Not Linear Set Union Algorithm
• Complexity of Monotone Networks for Computing Conjunctions
• Floats, Integers, and Single Source Shortest Paths