Minimum cuts and minimizing symmetric set functions

Romeo Rizzi

http://www.dimi.uniud.it/~rrizzi

Abstract:

In 1992, Nagamochi and Ibaraki gave an elegant and efficient algorithm to compute the edge-connectivity of an undirected graph, and, more generally, to find global cuts of minimum weight in undirected graphs. In 1995, Maurice Queyranne extended their approach to minimize symmetric submodular functions. With emphasis on simple arguments, we will be talking about:
1) this general approach;
2) the problem of finding minimum cuts in undirected graphs;
3) a more general problem on minimizing symmetric set functions.

The talk will serve as a simple introduction but will also present recent developments and new algorithms.

Key words: minimum cut algorithm, symmetric submodular functions, max-back order.