Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

DOI10.1016/j.tcs.2007.03.046zbMath1124.68006MaRDI QIDQ2383600

Aleksej Di Salvo, Guido Proietti

Publication date: 19 September 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.046

zbMATH Keywords

network survivability; swap algorithms; single source shortest paths tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68M10: Network design and communication in computer systems

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

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

Unnamed Item, Finding best swap edges minimizing the routing cost of a spanning tree, Stable routing under the Spanning Tree Protocol, A faster computation of all the best swap edges of a shortest paths tree, An improved algorithm for computing all the best swap edges of a tree spanner, Faster swap edge computation in minimum diameter spanning trees, A Faster Computation of All the Best Swap Edges of a Tree Spanner, Faster Swap Edge Computation in Minimum Diameter Spanning Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Swapping a failing edge of a single source shortest paths tree is good and fast
• Fast Algorithms for Finding Nearest Common Ancestors
• Efficiency of a Good But Not Linear Set Union Algorithm