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

DOI10.1007/S00453-012-9674-YMaRDI QIDQ476426zbMATH OpenOpenAlexFDO

Authors Luciano Gualà, Guido Proietti, D. 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

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

Recommendations

• Finding best swap edges minimizing the routing cost of a spanning tree
• The swap edges of a multiple-sources routing tree
• Swapping a failing edge of a single source shortest paths tree is good and fast
• 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

Cites work

• scientific article; zbMATH DE number 2086252 (Why is no real title available?)
• A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Algorithms and Computation
• Approximation algorithms for some optimum communication spanning tree problems
• Computing Best Swaps in Optimal Tree Spanners
• Fast Algorithms for Finding Nearest Common Ancestors
• Faster Swap Edge Computation in Minimum Diameter Spanning Trees
• Finding all the best swaps of a minimum diameter spanning tree under transient edge failures
• Finding the upper envelope of n line segments in O(n log n) time
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• Swapping a failing edge of a single source shortest paths tree is good and fast
• The complexity of the network design problem
• The swap edges of a multiple-sources routing tree
• Worst-Case Analysis of Network Design Problem Heuristics

Cited in

(13)

• An improved algorithm for computing all the best swap edges of a tree spanner
• The swap edges of a multiple-sources routing tree
• Finding best swap edges minimizing the routing cost of a spanning tree
• On the minimum routing cost clustered tree problem
• Efficient management of transient station failures in linear radio communication networks with bases
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem
• A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• Linear time distributed swap edge algorithms
• Linear time distributed swap edge algorithms
• A faster computation of all the best swap edges of a shortest paths tree
• Structural Information and Communication Complexity

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

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