Revision as of 14:46, 18 March 2009 edit Mebden (talk \| contribs) Extended confirmed users 2,036 edits No edit summary ← Previous edit		Revision as of 18:27, 25 March 2009 edit undo 128.173.98.90 (talk) →Approximation Algorithms Next edit →
Line 14: == Approximation Algorithms == 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 Fast Distributed Approximation Algorithm for Minimum Spanning Trees", ''Distributed Computing''. Pages 391-402, Vol. 20, No. 6, Apr. 2008.</ref>. This algorithm runs in <math>O(D+L~~\times~~\log n)</math> time, where <math>L</math> is the local shortest path diameter<ref name=khan/> of the graph. == Model ==

Distributed minimum spanning tree: Difference between revisions