A Survey on the Densest Subgraph Problem and Its Variants
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910414611152896 |
|---|---|
| author | Lanciano, Tommaso Miyauchi, Atsushi Fazzone, Adriano Bonchi, Francesco |
| author_facet | Lanciano, Tommaso Miyauchi, Atsushi Fazzone, Adriano Bonchi, Francesco |
| contents | The Densest Subgraph Problem requires 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14467 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Survey on the Densest Subgraph Problem and Its Variants Lanciano, Tommaso Miyauchi, Atsushi Fazzone, Adriano Bonchi, Francesco Data Structures and Algorithms Artificial Intelligence The Densest Subgraph Problem requires 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. |
| title | A Survey on the Densest Subgraph Problem and Its Variants |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2303.14467 |