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

DOI10.1016/S0020-0190(00)00175-7zbMath1013.68134WikidataQ127613489 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 path; graph algorithms; replacement shortest path; most vital edge; transient failure

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

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

05C38: Paths and cycles

Related Items

Unnamed Item, A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles, A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners, 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, 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, Incremental distance products via faulty shortest paths, Finding the anti-block vital edge of a shortest path between two nodes, Finding the most vital node of a shortest path., Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, An improved algorithm for computing all the best swap edges of a tree spanner, 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, Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, Optimal shortest path set problem in undirected graphs, Exact and approximate truthful mechanisms for the shortest paths tree problem, The swap edges of a multiple-sources routing tree, An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

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