THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
- 1 June 2004
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 15 (3), 507-516
- https://doi.org/10.1142/s0129054104002571
Abstract
In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity.Keywords
This publication has 4 references indexed in Scilit:
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning TreesSIAM Journal on Computing, 1998
- Distributed AlgorithmsPublished by Springer Science and Business Media LLC ,1994
- The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of ProcessorsSIAM Journal on Computing, 1987
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983