A fast distributed approximation algorithm for minimum spanning trees |
| |
Authors: | Maleq Khan Gopal Pandurangan |
| |
Affiliation: | (1) Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA |
| |
Abstract: | We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $H\,\in\,1, \Theta({\rm log} n)]We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time ?(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e.,
there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists
graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in
wireless networks and in random weighted networks in almost optimal ?(D(G)) time. |
| |
Keywords: | Minimum spanning tree Distributed approximation algorithm Randomized algorithm |
本文献已被 SpringerLink 等数据库收录! |
|