Content deleted Content added
m Bot: Automated text replacement (-\{\{[Cc]ite[ _][Dd][Oo][iI]/ +{{Cite doi|) |
→Further reading: The link should be refreshed. Isn't valid anymore |
||
| (12 intermediate revisions by 11 users not shown) | |||
Line 1:
| last1 = King | first1 = Valerie | author1-link = Valerie King
| title = A Simpler Minimum Spanning Tree Verification Algorithm
Line 28:
Example execution of a Borůvka step
{|
! Image !! Description
|-
Line 48:
===F-heavy and F-light edges===
In each iteration the algorithm removes edges with particular properties that exclude them from the [[minimum spanning tree]]. These are called ''F-heavy edges'' and are defined as follows. Let ''F'' be a forest on the [[Graph (discrete mathematics)|graph]] ''H''. An F-heavy edge is an edge ''e'' connecting vertices ''u'',''v'' whose weight is strictly greater than the weight of the heaviest edge on the path from ''u'' to ''v'' in ''F''. (If a path does not exist in ''F'' it is considered to have infinite weight). Any edge that is not F-heavy is ''F-light''. If ''
==Algorithm==
Line 65:
The expected performance is a result of the random sampling step. The effectiveness of the random sampling step is described by the following lemma which places a bound on the number of '''[[#F-heavy and F-light Edges|F-light]]''' edges in ''G'' thereby restricting the size of the second subproblem.
===Random
'''Lemma'''- Let ''H'' be a subgraph of ''G'' formed by including each edge of ''G'' independently with probability ''p'' and let ''F'' be the minimum spanning forest of ''H''. The [[Expected value|expected number]] of '''[[#F-heavy and F-light Edges|F-light]]''' edges in ''G'' is at most ''n/p'' where ''n'' is the number of vertices in ''G''
To prove the lemma examine the edges of ''G'' as they are being added to ''H''. The number of [[#F-heavy and F-light Edges|F-light]] edges in ''G'' is independent of the order in which the edges of ''H'' are selected since the minimum spanning forest of ''H'' is the same for all selection orders. For the sake of the proof consider selecting edges for ''H'' by taking the edges of ''G'' one at a time in order of edge weight from lightest to heaviest. Let ''e'' be the current edge being considered. If the endpoints of ''e'' are in two disconnected components of ''H'' then ''e'' is the lightest edge connecting those components and if it is added to ''H'' it will be in ''F'' by the [[Minimum_spanning_tree#Cut_property|cut property]]. This also means ''e'' is [[#F-heavy and F-light Edges|F-light]] regardless of whether or not it is added to ''H'' since only heavier edges are subsequently considered. If both endpoints of ''e'' are in the same component of ''H'' then it is (and always will be) F-heavy by the [[Minimum_spanning_tree#Cycle_property|cycle property]]. Edge ''e'' is then added to ''H'' with probability ''p''.
Line 72:
The maximum number of [[#F-heavy and F-light Edges|F-light]] edges added to ''H'' is ''n''-1 since any minimum spanning tree of ''H'' has ''n''-1 edges. Once ''n''-1 F-light edges have been added to ''H'' none of the subsequent edges considered are F-light by the [[Minimum_spanning_tree#Cycle_property|cycle property]]. Thus, the number of F-light edges in ''G'' is bounded by the number of F-light edges considered for ''H'' before ''n''-1 F-light edges are actually added to ''H''. Since any F-light edge is added with probability ''p'' this is equivalent to flipping a coin with probability ''p'' of coming up heads until ''n''-1 heads have appeared. The total number of coin flips is equal to the number of F-light edges in ''G''. The distribution of the number of coin flips is given by the [[negative binomial distribution|inverse binomial distribution]] with parameters ''n''-1 and ''p''. For these parameters the expected value of this distribution is (''n''-1)/''p''.
===Expected
Ignoring work done in recursive subproblems the total amount of work done in a single invocation of the algorithm is [[linear time|linear]] in the number of edges in the input graph. Step 1 takes constant time. Borůvka steps can be executed in time linear in the number of edges as mentioned in the [[#Borůvka step|Borůvka step]] section. Step 3 iterates through the edges and flips a single coin for each one so it is linear in the number of edges. Step 4 can be executed in linear time using a modified linear time minimum spanning tree verification algorithm.<ref name=MST-V1/><ref name=MST-V2/> Since the work done in one iteration of the algorithm is linear in the number of edges the work done in one complete run of the algorithm (including all recursive calls) is bounded by a constant factor times the total number of edges in the original problem and all recursive subproblems.
Line 90:
==References==
{{Reflist}}
[[Category:Randomized algorithms]]
| |||