Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems

Daniela Scherer dos Santos, Kathrin Klamroth, Pedro Martins +1

Given an undirected graph $G$, a quasi-clique is a subgraph of $G$ whose density is at least $\gamma$ $(0<\gamma \le 1)$. Two optimization problems can be defined for quasi-cliques: the Ma…