Approximation Algorithms
An -approximation algorithm was developed by Maleq Khan and Gopal Pandurangan. This algorithm runs in time, where is the local shortest path diameter of the graph.
Read more about this topic: Distributed Minimum Spanning Tree