Finding the most vital node of a shortest path.

DOI10.1016/S0304-3975(02)00438-3zbMath1044.68132MaRDI QIDQ1401266

Guido Proietti, Peter Widmayer, Enrico Nardelli

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Shortest pathMechanism designNetwork survivabilityNode vitality

Mathematics Subject Classification ID

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

Related Items (14)

The impact of dynamic events on the number of errors in networks ⋮ A simple algorithm for replacement paths problem ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ Shortest paths with shortest detours. A biobjective routing problem ⋮ Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs ⋮ Faster swap edge computation in minimum diameter spanning trees ⋮ On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Exact and approximate truthful mechanisms for the shortest paths tree problem ⋮ Fault-tolerant approximate shortest-path trees ⋮ Strongly polynomial-time truthful mechanisms in one shot ⋮ Finding the anti-block vital edge of a shortest path between two nodes ⋮ Incremental distance products via faulty shortest paths ⋮ Unnamed Item

Cites Work

• A note on two problems in connexion with graphs
• Finding the detour-critical edge of a shortest path between two nodes
• NC algorithms for the Single Most Vital Edge problem with respect to shortest paths
• The k most vital arcs in the shortest path problem
• Most vital links and nodes in weighted networks
• A faster computation of the most vital edge of a shortest path
• Finding the most vital arcs in a network
• Algorithmic mechanism design (extended abstract)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Finding the most vital node of a shortest path.