The first approximated distributed algorithm for the minimum degree spanning tree problem on general graphs

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 gives 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.