Content deleted Content added
→Min cut: format code |
|||
Line 100:
[[File:Contraction vertices.jpg|300px|thumb|center|Figure 1: Contraction of vertex A and B]]
Karger's<ref>A. A. Tsay, W. S. Lovejoy, David R. Karger, ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.215.794&rep=rep1&type=pdf Random Sampling in Cut, Flow, and Network Design Problems]'', Mathematics of Operations Research, 24(2):383–413, 1999.</ref> basic algorithm:
i = 1
'''repeat'''
'''repeat'''
Take a random edge (u,v)∈ E in G
replace u and v with the contraction u'
'''until''' only 2 nodes remain
obtain the corresponding cut result C<sub>i</sub>
i = i + 1
'''until''' i = m
output the minimum cut among C<sub>1</sub>, C<sub>2</sub>, ..., C<sub>m</sub>.
In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is <math>O(n)</math>, and ''n'' denotes the number of vertices.
After ''m'' times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives an
| |||