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

DOI10.4230/LIPICS.ISAAC.2018.7MaRDI QIDQ5090997zbMATH OpenOpenAlexFDO

Authors D. Bilò, Kleitos Papadopoulos

Publication date 21 July 2022

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

zbMATH Keywords

best swap edgestransient edge failuretree spanner

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• An improved algorithm for computing all the best swap edges of a tree spanner
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• Effective edge-fault-tolerant single-source spanners via best (or good) swap edges
• Computing all best swaps for minimum-stretch tree spanners

Cites work

• A faster computation of all the best swap edges of a shortest paths tree
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• A faster computation of the most vital edge of a shortest path
• Algorithms and Computation
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• Computing all best swaps for minimum-stretch tree spanners
• Computing all the best swap edges distributively
• Effective edge-fault-tolerant single-source spanners via best (or good) swap edges
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding best swap edges minimizing the routing cost of a spanning tree
• scientific article; zbMATH DE number 2163017 (Why is no real title available?)
• Maintaining spanning trees of small diameter
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The level ancestor problem simplified
• The swap edges of a multiple-sources routing tree

Cited in

(7)

• An improved algorithm for computing all the best swap edges of a tree spanner
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• Computing Best Swaps in Optimal Tree Spanners
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• An edge-swap heuristic for finding dense spanning trees
• Principles of Distributed Systems
• A tight bound on the size of a smallest critical set for each failed edge in a tree spanner

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090997)