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

2017-01-10   10:00 ~ 11:00   

Speaker

Chao Xu, University of Illinois at Urbana-Champaign

Room

Room 308, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics