A faster computation of all the best swap edges of a shortest paths tree

DOI10.1007/S00453-014-9912-6MaRDI QIDQ893317zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luciano Gualà, Guido Proietti

Publication date 19 November 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-014-9912-6

zbMATH Keywords

edge fault tolerancesingle-source shortest paths treeswap algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A faster computation of all the best swap edges of a shortest paths tree
• Structural Information and Communication Complexity
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• Publication:4938662
• Swapping a failing edge of a single source shortest paths tree is good and fast

Cites work

• scientific article; zbMATH DE number 1405681 (Why is no real title available?)
• A faster computation of all the best swap edges of a shortest paths tree
• Algorithms and Computation
• Exact and approximate truthful mechanisms for the shortest paths tree problem
• Fast Algorithms for Finding Nearest Common Ancestors
• Faster swap edge computation in minimum diameter spanning trees
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding all the best swaps of a minimum diameter spanning tree under transient edge failures
• Finding best swap edges minimizing the routing cost of a spanning tree
• Maintaining spanning trees of small diameter
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• Strict Fibonacci heaps
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• The swap edges of a multiple-sources routing tree

Cited in

(11)

• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• Principles of Distributed Systems
• Structural Information and Communication Complexity
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• Linear time distributed swap edge algorithms
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• An improved algorithm for computing all the best swap edges of a tree spanner
• Swapping a failing edge of a single source shortest paths tree is good and fast
• A faster computation of all the best swap edges of a shortest paths tree
• Computing Best Swaps in Optimal Tree Spanners
• A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

This page was built for publication: A faster computation of all the best swap edges of a shortest paths tree

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