Distributed minimum spanning tree: Difference between revisions

Revision as of 17:34, 11 July 2009

Revision as of 23:05, 31 August 2009

Line 1:

The '''distributed minimum spanning tree''' problem involves the construction of a [[minimum spanning tree]] by a [[distributed algorithm]], in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles [[Borůvka's algorithm]].

The problem was first suggested and solved in <math>O(V \log V)</math> time in 1983 by GallagherGallager et al. <ref>[[Robert G. Gallager]], Pierre A. Humblet, and P. M. Spira, "A“A distributed algorithm for minimum-weight spanning trees,"” ''ACM TOPLASTransactions on Programming Languages and Systems'', vol. 5, no. 1, pp. 66--7766–77, January 1983.</ref>, where <math>V</math> is the number of vertices in the [[graph theory|graph]]. Later the solution was improved to <math>O(V)</math>

<ref>[[Baruch Awerbuch]]. Optimal“Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems.,” ''Proceedings of the 19th Annual ACM [[Symposium on Theory of Computing]] (STOC)'', New York City, New York, May 1987.

</ref> and finally

<ref>Juan Garay, Shay Kutten and [[David Peleg]], "A“A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)",” ''Proceedings of the IEEE [[Symposium on Foundations of Computer Science]]'' (FOCS), 1993.</ref>

<math>O(\sqrt V \log^* V + D)</math>

where ''D'' is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be

<ref>David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction”Construction,“ ''[[SIAM Journal ofon Computing]]'', 2000, and ''IEEE Symposium on Foundations of Computer Science (FOCS) Symposium'', 1999.</ref>

<math>\Omega\left({\frac{\sqrt V}{\log V}}\right).</math>

== Approximation Algorithmsalgorithms ==

An <math>O(\log n)</math>-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan<ref name="khan"> Maleq Khan and Gopal Pandurangan. "A“A Fast Distributed Approximation Algorithm for Minimum Spanning Trees",” ''Distributed Computing''. Pages 391-402, Volvol. 20, Nono. 6, pp. 391–402, Apr. 2008.</ref>. This algorithm runs in <math>O(D+L\log n)</math> time, where <math>L</math> is the local shortest path diameter<ref name=khan/> of the graph.

== Model ==

Line 31:

[[Category:Spanning tree]]

[[Category:Distributed algorithms]]