| Proof Outline |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Graph
has O(n2)
(capacitated) edges |
|||||||||||
| l | So O(n2) work to contract, then two |
|||||||||||
| subproblems of
size n/2½ |
||||||||||||
| » | T(n) = 2 T(n/2½) + O(n2)
= O(n2 log n) |
|||||||||||
| l | Algorithm fails
if both iterations fail |
|||||||||||
| » | Iteration
succeeds if contractions and |
|||||||||||
| recursion succeed |
||||||||||||
| » | P(n)=1 - [1 - ½ P(n/2½)]2
= W (1 / log n) |
|||||||||||