A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
Krzysztof Krzywdzinski
Abstract
We present a new distributed algorithm, which finds a good approximation
of the Minimum Spanning Tree in the Unit Disc Graphs. Our algorithm, in
O(d^2) synchronous rounds, where d is an input parameter, finds a
subgraph H of the Unit Disc Graph G which contains a Minimum Spanning
Tree of G. Moreover, H is planar, does not contain cycles of weight
smaller than d/3 and the weight of H is (1+O(1/d)) approximation of the
weight of the Minimum Spanning Tree of G.