Finding densest subgraphs is a fundamental problem in graph mining, with several applications in different fields. In this paper, we consider two variants of the problem of covering a graph with k densest subgraphs, where k≥ 2. The first variant aims to find a collection of k subgraphs of maximum density, the second variant asks for a set of k subgraphs such that they maximize an objective function that includes the sum of the subgraphs densities and a distance function, in order to differentiate the computed subgraphs. We show that the first variant of the problem is solvable in polynomial time, for any k≥ 2. For the second variant, which is NP-hard for k≥ 3, we present an approximation algorithm that achieves a factor of 2/5.

(2022). Covering a Graph with Densest Subgraphs . Retrieved from https://hdl.handle.net/10446/234249

Covering a Graph with Densest Subgraphs

Dondi, Riccardo;Popa, Alexandru
2022-01-01

Abstract

Finding densest subgraphs is a fundamental problem in graph mining, with several applications in different fields. In this paper, we consider two variants of the problem of covering a graph with k densest subgraphs, where k≥ 2. The first variant aims to find a collection of k subgraphs of maximum density, the second variant asks for a set of k subgraphs such that they maximize an objective function that includes the sum of the subgraphs densities and a distance function, in order to differentiate the computed subgraphs. We show that the first variant of the problem is solvable in polynomial time, for any k≥ 2. For the second variant, which is NP-hard for k≥ 3, we present an approximation algorithm that achieves a factor of 2/5.
File allegato/i alla scheda:
File Dimensione del file Formato  
CALDAM2022.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 255.27 kB
Formato Adobe PDF
255.27 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/234249
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact