THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS

DOI10.1142/S0129054104002571zbMath1067.68790OpenAlexW1540674943MaRDI QIDQ3022016

Franck Butelle, Lélia Blin

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054104002571

zbMATH Keywords

distributed algorithmsspanning treesasynchronous algorithmsminimum degree spanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (3)

Self-stabilizing minimum degree spanning tree within one from the optimal degree ⋮ A distributed approximation algorithm for the minimum degree minimum weight spanning trees ⋮ Maximum metric spanning tree made Byzantine tolerant

Cites Work

• Unnamed Item
• Distributed algorithms. 8th international workshop, WDAG 1994, Terschelling, The Netherlands, September 29 -- October 1, 1994. Proceedings
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

This page was built for publication: THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS