Vertex Sparsifiers for c-Hyperedge Connectivity
- LecturerDr. Shang-En Huang (Boston College)
Host: Meng-Tsung Tsai - Time2022-08-24 (Wed.) 10:00 ~ 12:00
- LocationAuditorium106 at IIS new Building
Abstract
Recently, Chalermsook et al. [SODA'21] introduces a notion of vertex sparsifiers for c-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for c-edge st-connectivity [Jin and Sun FOCS'21]. We study a natural extension called vertex sparsifiers for c-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs.
In this talk, I will briefly give an introduction to vertex sparsifiers, present Chalermsook et al.'s result on vertex sparsifiers for edge connectivity, and our results on hypergraphs.
More details can be found in https://arxiv.org/pdf/2207.04115.pdf .
In this talk, I will briefly give an introduction to vertex sparsifiers, present Chalermsook et al.'s result on vertex sparsifiers for edge connectivity, and our results on hypergraphs.
More details can be found in https://arxiv.org/pdf/2207.04115.pdf .