Computing minimum cuts in hypergraphs (Chao Xu)

Abstract

Given a hypergraph H = (V, E) with n = |V|, m = |E| and p = sum of degrees, the fastest known algorithm to compute a global minimum cut in H runs in O(np + n^2 log n) time.

I will show some results on graphs that can be generalized to hypergraphs and focuses on the algorithmic problem of finding a structure that represents *all* mincuts. The algorithm uses Cunningham’s decomposition framework, and different generalizations of maximum adjacency ordering, and has a running time of O(np + n^2 log n), which matches the running time of finding a single mincut.

The talk is based on a joint work with Chandra Chekuri. The latest version can be found at https://arxiv.org/abs/1607.08682

Time

Speaker

Room