An improved algorithm for computing all the best swap edges of a tree spanner

DOI10.1007/s00453-019-00549-wzbMath1433.68281OpenAlexW2953579640WikidataQ128527417 ScholiaQ128527417MaRDI QIDQ1986961

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

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8266/

zbMATH Keywords

tree spannerswap algorithmtransient edge failure

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• 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
• 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
• 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

This page was built for publication: An improved algorithm for computing all the best swap edges of a tree spanner