A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

DOI10.4230/LIPIcs.ISAAC.2018.7OpenAlexW2963059035MaRDI QIDQ5090997

Kleitos Papadopoulos, Davide Bilò

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1807.01260

zbMATH Keywords

tree spannertransient edge failurebest swap edges

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Computing all the best swap edges distributively
• Finding best swap edges minimizing the routing cost of a spanning tree
• The level ancestor problem simplified
• A faster computation of all the best swap edges of a shortest paths tree
• Maintaining spanning trees of small diameter
• A faster computation of the most vital edge of a shortest path
• Effective edge-fault-tolerant single-source spanners via best (or good) swap edges
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The swap edges of a multiple-sources routing tree
• Computing All Best Swaps for Minimum-Stretch Tree Spanners
• Fast Algorithms for Finding Nearest Common Ancestors
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• Algorithms and Computation

This page was built for publication: A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners