A faster computation of the most vital edge of a shortest path
From MaRDI portal
Publication:1603442
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
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
