A Faster Computation of All the Best Swap Edges of a Tree Spanner

DOI10.1007/978-3-319-25258-2_17zbMath1471.68186OpenAlexW2293523301MaRDI QIDQ3460719

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

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (4)

An improved algorithm for computing all the best swap edges of a tree spanner ⋮ A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners ⋮ Linear time distributed swap edge algorithms ⋮ An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

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
• 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
• Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
• Maintaining information in fully dynamic trees with top trees
• Computing All Best Swaps for Minimum-Stretch Tree Spanners
• Fast Algorithms for Finding Nearest Common Ancestors
• 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: A Faster Computation of All the Best Swap Edges of a Tree Spanner