Linear time distributed swap edge algorithms

DOI10.1016/j.ipl.2020.105979zbMath1441.68173OpenAlexW59179063MaRDI QIDQ783711

Linda Pagli, Lawrence L. Larmore, Ajoy K. Datta, Giuseppe Prencipe, Paolo Ferragina

Publication date: 4 August 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105979

zbMATH Keywords

fault tolerancedistributed computingdistributed algorithmsedge failureswap edges

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) Connectivity (05C40) Distributed algorithms (68W15) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Computing all the best swap edges distributively
• Finding best swap edges minimizing the routing cost of a spanning tree
• A faster computation of all the best swap edges of a shortest paths tree
• Swapping a failing edge of a single source shortest paths tree is good and fast
• Nearly linear time minimum spanning tree maintenance for transient node failures
• Design and Analysis of Distributed Algorithms
• A Faster Computation of All the Best Swap Edges of a Tree Spanner
• Linear Time Distributed Swap Edge Algorithms
• Distributed Minimum Spanning Tree Maintenance for Transient Node Failures