Nearly linear time minimum spanning tree maintenance for transient node failures

DOI10.1007/s00453-004-1099-9zbMath1088.68143OpenAlexW2123839217MaRDI QIDQ1882530

Enrico Nardelli, Guido Proietti, Peter Widmayer

Publication date: 1 October 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/313840/files/453_2004_Article_1099.pdf

zbMATH Keywords

Fault toleranceMinimum spanning treeGraph algorithmsAlgorithmic mechanism designTransient node failures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (5)

Faster swap edge computation in minimum diameter spanning trees ⋮ Exact and approximate truthful mechanisms for the shortest paths tree problem ⋮ An improved algorithm for computing all the best swap edges of a tree spanner ⋮ Linear time distributed swap edge algorithms ⋮ An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

This page was built for publication: Nearly linear time minimum spanning tree maintenance for transient node failures