Loading...
Please wait, while we are loading the content...
Similar Documents
A fast distributed approximation algorithm for minimum spanning trees (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Pandurangan, Gopal Khan, Maleq |
| Description | IN PROCEEDINGS OF THE 20TH INTERNATIONAL SYMPOSIUM ON DISTRIBUTED COMPUTING (DISC |
| 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 exists graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H ∈ [1, Θ(log n)]. 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. |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Approximate Mst Wireless Network Distributed Algorithm Time-optimal Distributed Algorithm Approximate Minimum Spanning Tree Approximate Mst Computation Path Diameter Minimum Spanning Tree Significant Time Gap Running Time Fast Distributed Approximation Algorithm Polylogarithmic Factor Approximation Algorithm Arbitrary Network |
| Content Type | Text |
| Resource Type | Proceeding |
