Lydia Mendoza: Isolating cuts, (bi)submodularity and faster algorithms for connectivity (Paper by Chekuri and Quanrud)

ELTE Alkalmazott Diszkrét Matematika szeminárium

Abstract:
What do element connectivity and vertex connectivity have in common? In this
talk, we will discuss one algorithm that can solve these two problems, among
others. This approach is a generalization of the fist deterministic algorithm
that determines the global minimum cut of a weighted undirected graph. The
later algorithm is based on isolating cuts.

The technique that the authors use is based on crossing lattices, and
symmetric and (bi)submodular functions. The goal is to find an isolating cut
on a more general framework that can be reduced to solve connectivity problems
in different settings as hypergraphs, element connectivity and vertex
connectivity in graphs.