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

DOI10.1007/s00453-014-9912-6zbMath1325.68167OpenAlexW2173847299MaRDI QIDQ893317

Guido Proietti, Luciano Gualà, Davide Bilò

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

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

Related Items (5)

A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ 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
• Maintaining spanning trees of small diameter
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• Faster swap edge computation in minimum diameter spanning trees
• Exact and approximate truthful mechanisms for the shortest paths tree problem
• The swap edges of a multiple-sources routing tree
• Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
• A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree
• Fast Algorithms for Finding Nearest Common Ancestors
• Fibonacci heaps and their uses in improved network optimization algorithms
• Strict fibonacci heaps
• Algorithms and Computation

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