Counting small cuts in a graph

Barbara Geissmann, Rastislav Šrámek

We study the minimum cut problem in the presence of uncertainty and show how to apply a novel robust optimization approach, which aims to exploit the similarity in subsequent graph…