MIT
84
NI Certificate Algorithm
lRepeat
k
times
»Find
a spanning forest
»Delete
it
lEach
iteration deletes one edge from every cut (forest is
spanning)
lSo
at end, any edge crossing a cut of size £ k is deleted
l[NI]
pipeline all iterations in O(m) time