Optimal maintenance of a spanning tree

DOI10.1145/1391289.1391292MaRDI QIDQ3452184zbMATH OpenOpenAlexFDO

Authors Baruch Awerbuch, Israel Cidon, Shay Kutten

Publication date 11 November 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1391289.1391292

zbMATH Keywords

amortized complexitydistributed algorithmsdynamic networksleader electionoptimal message complexityspanning treetopological changes

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Maintenance of a Spanning Tree For Dynamic Graphs by Mobile Agents and Local Computations
• Maintaining minimum spanning trees in dynamic graphs
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Distributed communication complexity of spanning tree construction

Cited in

(5)

• Optimal Broadcast with Partial Knowledge
• Maintaining spanning trees of small diameter
• Multi-period maintenance scheduling of tree networks with minimum flow disruption
• The slide mechanism with applications in dynamic networks (extended abstract)
• Optimal Broadcast with Partial Knowledge

This page was built for publication: Optimal maintenance of a spanning tree

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