On Finding Dense Subgraphs

By Samir Khuller, B. Saha. International Colloquium on Automata, Languages and Programming, 2009

305 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Entity Linking meets Word Sense Disambiguation: a Unified Approach (2014, methodology): “Therefore, we define a heuristic for k-partite graphs inspired by a 2-approximation greedy algorithm for arbitrary graphs (Charikar, 2000; Khuller and Saha, 2009).”
On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, unknown): “This problem is a particular variant of the general problem of finding large dense subgraphs in bipartite graphs; see, e.g., [3, 23, 24] and the references therein.”
The community-search problem and how to plan a successful cocktail party (2010, background): “Recently, Andersen and Chellapilla [2] and subsequently Khuller and Saha [20] studied the case with lower bound and upper bound constraints.”
Truncated power method for sparse eigenvalue problems (2011, methodology): “…of algorithms have been proposed based on a variety of techniques including greedy algorithms (Feige et al., 2001; Asahiro et al., 2002; Ravi et al., 1994), linear programming (Billionnet & Roupin, 2004; Khuller & Saha, 2009), and semideﬁnite programming (Srivastav & Wolf, 1998; Ye & Zhang, 2003).”
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, unknown): “Problem 1 ( optimal ( g, h, α ) -edge-surplus ).”