Swapping a failing edge of a single source shortest paths tree is good and fast

DOI10.1007/s00453-002-0988-zzbMath1026.68102OpenAlexW2007776707MaRDI QIDQ1566374

Enrico Nardelli, Guido Proietti, Peter Widmayer

Publication date: 2 June 2003

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-002-0988-z

zbMATH Keywords

network survivabilityswap algorithmssingle source shortest paths tree

Mathematics Subject Classification ID

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

Related Items (14)

Dense trees: a new look at degenerate graphs ⋮ Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Stable routing under the Spanning Tree Protocol ⋮ Faster swap edge computation in minimum diameter spanning trees ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Computing all the best swap edges distributively ⋮ A theory and algorithms for combinatorial reoptimization ⋮ Faster Swap Edge Computation in Minimum Diameter Spanning Trees ⋮ Finding best swap edges minimizing the routing cost of a spanning tree ⋮ The swap edges of a multiple-sources routing tree ⋮ Single backup table schemes for shortest-path routing ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Linear time distributed swap edge algorithms

This page was built for publication: Swapping a failing edge of a single source shortest paths tree is good and fast