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

DOI10.1142/S0129054104002571MaRDI QIDQ3022016zbMATH OpenOpenAlexFDO

Authors Lélia Blin, Franck Butelle

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

spanning treesdistributed algorithmsasynchronous algorithmsminimum degree spanning trees

Mathematics Subject Classification ID

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

Recommendations

• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• scientific article; zbMATH DE number 742978
• A distributed algorithm for constructing a minimum diameter spanning tree
• scientific article; zbMATH DE number 749817
• scientific article; zbMATH DE number 4058884

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• 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

Cited in

(6)

• A fully asynchronous and fault tolerant distributed algorithm to compute a minimum graph orientation
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• Distributed Minimum Degree Spanning Trees
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• Self-stabilizing minimum degree spanning tree within one from the optimal degree

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

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