A Survey on the Densest Subgraph Problem and its Variants
Top Cited Papers
Open Access
- 30 April 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 56 (8) , 1-40
Abstract
The Densest Subgraph Problem requires us to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.Keywords
All Related Versions
This publication has 187 references indexed in Scilit:
- In search of dense subgraphs: How good is greedy peeling?Networks, 2021
- Discounted average degree density metric and new algorithms for the densest subgraph problemNetworks, 2017
- Distance-Based Clique Relaxations in Networks: s-Clique and s-Club2013
- A Survey of Algorithms for Dense Subgraph Discovery2010
- Approximation Algorithms for Maximization Problems Arising in Graph PartitioningJournal of Algorithms, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Greedily Finding a Dense SubgraphJournal of Algorithms, 2000
- Generating Sparse 2-SpannersJournal of Algorithms, 1994
- A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theoryNetworks, 1982