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