An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

DOI10.4230/LIPIcs.ISAAC.2017.14zbMath1457.68205arXiv1710.01516OpenAlexW2964019098MaRDI QIDQ5136230

Stefano Leucci, Feliciano Colella, Guido Proietti, Luciano Gualà, Davide Bilò

Publication date: 25 November 2020

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

zbMATH Keywords

tree spannerswap algorithmtransient edge failure

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

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

Cites Work

• Finding best swap edges minimizing the routing cost of a spanning tree
• A faster computation of all the best swap edges of a shortest paths tree
• Maintaining spanning trees of small diameter
• Effective edge-fault-tolerant single-source spanners via best (or good) swap edges
• Single backup table schemes for shortest-path routing
• Nearly linear time minimum spanning tree maintenance for transient node failures
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The zoo of tree spanner problems
• The swap edges of a multiple-sources routing tree
• Maintaining information in fully dynamic trees with top trees
• Computing All Best Swaps for Minimum-Stretch Tree Spanners
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Tree Spanners
• Algorithms and Computation
• Unnamed Item
• Unnamed Item

This page was built for publication: An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner