Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser

Vertex Sparsifiers for c-Hyperedge Connectivity


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
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 .