An improved algorithm for computing all the best swap edges of a tree spanner
type: Item
instance of: scholarly article
title: An improved algorithm for computing all the best swap edges of a tree spanner
zbMATH Open document ID: 1433.68281
author: D. Bilò
author: Feliciano Colella
author: Luciano Gualà
author: Stefano Leucci
author: Guido Proietti
published in: Algorithmica
publication date: 2020-04-09T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8266/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7188811
zbMATH Keywords: transient edge failure
zbMATH Keywords: swap algorithm
zbMATH Keywords: tree spanner
MaRDI profile type: Publication
OpenAlex ID: W2953579640
cites work: Q2934632
cites work: Maintaining information in fully dynamic trees with top trees
cites work: A Faster Computation of All the Best Swap Edges of a Tree Spanner
cites work: Effective edge-fault-tolerant single-source spanners via best (or good) swap edges
cites work: Finding best swap edges minimizing the routing cost of a spanning tree
cites work: A faster computation of all the best swap edges of a shortest paths tree
cites work: Distance Approximating Trees for Chordal and Dually Chordal Graphs
cites work: Tree Spanners
cites work: Computing All Best Swaps for Minimum-Stretch Tree Spanners
cites work: Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
cites work: Maintaining spanning trees of small diameter
cites work: The zoo of tree spanner problems
cites work: A faster computation of the most vital edge of a shortest path
cites work: Nearly linear time minimum spanning tree maintenance for transient node failures
cites work: Algorithms and Computation
cites work: Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
cites work: The swap edges of a multiple-sources routing tree
Wikidata QID: Q128527417
DOI: 10.1007/S00453-019-00549-W
Recommended article: An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
Recommended article: A Faster Computation of All the Best Swap Edges of a Tree Spanner
Recommended article: A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
Recommended article: A faster computation of all the best swap edges of a shortest paths tree
Recommended article: A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree
Recommended article: Computing Best Swaps in Optimal Tree Spanners
Recommended article: Computing All Best Swaps for Minimum-Stretch Tree Spanners
Recommended article: An edge-swap heuristic for finding dense spanning trees
Recommended article: Q4673402
Recommended article: A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
description: scientific article; zbMATH DE number 7188811