Content deleted Content added
No edit summary Tags: Reverted categories removed Mobile edit Mobile web edit |
Reverted 1 edit by 189.156.187.30 (talk): Rv; removed for no reason |
||
Line 93:
== Approximation algorithms ==
An <math>O(\log n)</math>-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.<ref name="Khan" /> 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.
== References ==
<references>
<ref name="GHS">[[Robert G. Gallager]], Pierre A. Humblet, and P. M. Spira, "A distributed algorithm for minimum-weight spanning trees," ''ACM Transactions on Programming Languages and Systems'', vol. 5, no. 1, pp. 66–77, January 1983.</ref>
<ref name="Khan">Maleq Khan and Gopal Pandurangan. "A Fast Distributed Approximation Algorithm for Minimum Spanning Trees,"" ''Distributed Computing'', vol. 20, no. 6, pp. 391–402, Apr. 2008.</ref>
<ref name="Lynch">Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.</ref>
</references>
[[Category:Spanning tree]]
[[Category:Distributed algorithms]]
| |||