Graph Cuts and Vertex Sparsifiers |
|
---|---|
![]() Prof. Syamantak Das, CSE, IIITD
Short Bio: Date:June 25, 2020 |
Abstract:
Graph compression or sparsification is a basic information-theoretic and computational question of the following nature: given a graph G, can we compute a “compact” representation of G, with potentially fewer vertices or edges, that preserves important information? Such objects play a major role in the design of efficient graph algorithms and thus have been a centre of study for decades. For instance, the notion of graph spanners aims to preserve the distance between nodes in the graphs while reducing the number of edges, while the notion of vertex sparsification focuses on preserving some properties of the designated nodes such as connectivity, cut sizes, or effective resistance.
In this talk, I shall mostly do a survey of vertex sparsification of graphs and try to establish its connections to various algorithmic problems related to graphs both in the static and the dynamic setting
|