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