Events by date

Title: Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

Speaker: Chandra Chekuri Affiliation: University of Illinois, Urbana-Champaign Zoom: Please email Emma Watson

Abstract:

The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis.