MIT
83
Construction
lTo
sample, must find edge strengths
»can’t,
but approximation suffices
lSparse certificates identify
weak edges:
»construct
in linear time [NI]
»contain
all edges crossing cuts £ k
»iterate
until strong components emerge
lIterate
for 2i-strong edges, all i
»tricks
turn it strongly polynomial