Greedy approximation algorithms for finding dense components in a graph

By Moses Charikar. International Workshop on Approximation Algorithms for Combinatorial Optimization, 2000

622 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.

Identification of functional modules using network topology and high-throughput data (2007, methodology): “This method is inspired by Charikar's 2-approximation algorithm for the densest subgraph problem [ 46 ].”
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, methodology): “Charikar [10] shows that the greedy algorithm proposed by Asashiro et al.”
FRAUDAR: Bounding Graph Fraud in the Face of Camouflage (2016, background): “to ours is Charikar’s work on finding subgraphs with large average degree [4], which shows that subgraph average degree can be optimized with approximation guarantees.”
Entity Linking meets Word Sense Disambiguation: a Unified Approach (2014, methodology): “Therefore, we deﬁne a heuristic for k -partite graphs inspired by a 2-approximation greedy algorithm for arbitrary graphs (Charikar, 2000; Khuller and Saha, 2009).”
The community-search problem and how to plan a successful cocktail party (2010, methodology): “Our algorithm, called Greedy , is a variant of the greedy al-gorithm that was proposed and studied by Asahiro et al. [4] and later analyzed by Charikar [7], who showed that it achieves a factor 2 approximation guarantee for the densest-subgraph problem.”
Local Modeling of Attributed Graphs: Algorithms and Applications (2016, methodology): “average degree, edge density) and have been used for dense subgraph mining [28, 139] and anomaly detection [2].”