Search

Abstract: We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most , where is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is where is the number of edges and is the number of nodes. The memory complexity is in the send–receive atomicity model ( is the maximal degree of the network). [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]