Finding best swap edges minimizing the routing cost of a spanning tree

DOI10.1007/s00453-012-9674-yzbMath1317.68063OpenAlexW1999704039MaRDI QIDQ476426

Guido Proietti, Luciano Gualà, Davide Bilò

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9674-y

zbMATH Keywords

graph algorithmstransient edge failuresall-best swap edges problemsminimum routing-cost spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (8)

On the minimum routing cost clustered tree problem ⋮ A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem ⋮ A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ A faster computation of all the best swap edges of a shortest paths tree ⋮ 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 the upper envelope of n line segments in O(n log n) time
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Swapping a failing edge of a single source shortest paths tree is good and fast
• Approximation algorithms for some optimum communication spanning tree problems
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The swap edges of a multiple-sources routing tree
• Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
• Fast Algorithms for Finding Nearest Common Ancestors
• A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
• Faster Swap Edge Computation in Minimum Diameter Spanning Trees
• Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
• Computing Best Swaps in Optimal Tree Spanners
• Worst-Case Analysis of Network Design Problem Heuristics
• The complexity of the network design problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Algorithms and Computation

This page was built for publication: Finding best swap edges minimizing the routing cost of a spanning tree