Self-stabilizing minimum degree spanning tree within one from the optimal degree

DOI10.1016/j.jpdc.2010.08.019zbMath1219.68036MaRDI QIDQ635330

Maria Gradinariu Potop-Butucaru, Lélia Blin, Stephane Rovedakis

Publication date: 19 August 2011

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpdc.2010.08.019

zbMATH Keywords

self-stabilization; message passing networks; minimum degree spanning tree

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68M14: Distributed systems

68W15: Distributed algorithms

Related Items

Maximum metric spanning tree made Byzantine tolerant, Self-stabilizing minimum degree spanning tree within one from the optimal degree, A deterministic worst-case message complexity optimal solution for resource discovery, A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks, A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• Self-stabilizing minimum degree spanning tree within one from the optimal degree
• Self-stabilization of dynamic systems assuming only read/write atomicity
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Self-stabilizing systems in spite of distributed control
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal