Finding Connected Dense $k$-Subgraphs

Xujin Chen, Xiaodong Hu, Changjun Wang

Given a connected graph $G$ on $n$ vertices and a positive integer $k\le n$, a subgraph of $G$ on $k$ vertices is called a $k$-subgraph in $G$. We design combinatorial approximatio…