Borůvka's algorithm: Difference between revisions

Content deleted Content added
Complexity: complexity is not "obviously correct"
Complexity: admittedly m < n is quite an uncommon case
Line 69:
== Complexity ==
 
Borůvka's algorithm can be shown to take [[Big O notation|O]](log ''V'') iterations of the outer loop until it terminates, and therefore to run in time [[Big O notation|O]](''E'' log ''V''), where ''E'' is the number of edges, and ''V'' is the number of vertices in ''G''.{{dubious|reason=In case(assuming m''E'' &lt; n, finding connected components and checking their cheapest edge can take more than O(m''V'') time.}} In [[planar graph]]s, and more generally in families of graphs closed under [[graph minor]] operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm.<ref>{{Cite book|last=Eppstein|first=David|author-link=David Eppstein|contribution=Spanning trees and spanners|title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link= Jorge Urrutia Galicia|publisher=Elsevier|year=1999|pages=425–461}}; {{Cite journal|last=Mareš|first=Martin|title=Two linear time algorithms for MST on minor closed graph classes|journal=Archivum Mathematicum|volume=40|year=2004|issue=3|pages=315–320|url=http://www.emis.de/journals/AM/04-3/am1139.pdf}}.</ref>
 
== Example ==