Aisberg: dal 2009 è l'archivio ad accesso aperto dell'Università di Bergamo; dal 2011 è anche l'anagrafe della ricerca di Ateneo.
L'archivio è un'implementazione di IRIS, il sistema informativo per la ricerca sviluppato da Cineca.
EnglishWe study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t≥2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s=2, t=3 and r=|V|. Moreover, we show that the problem is polynomial-time solvable when s≥4, t=3 and r=|V|, and when s≥3, t=2 and r=|V|. Finally, for s≥2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices.
(2019). On the tractability of finding disjoint clubs in a network [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/150297
| Citazione: | (2019). On the tractability of finding disjoint clubs in a network [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/150297 | |
| Titolo: | On the tractability of finding disjoint clubs in a network | |
| Tipologia specifica: | articolo | |
| Tutti gli autori: | Dondi, Riccardo; Mauri, Giancarlo; Zoppis, Italo | |
| Data di pubblicazione: | 2019 | |
| Abstract (eng): | We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t≥2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s=2, t=3 and r=|V|. Moreover, we show that the problem is polynomial-time solvable when s≥4, t=3 and r=|V|, and when s≥3, t=2 and r=|V|. Finally, for s≥2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices. | |
| Rivista: | ||
| Nelle collezioni: | 1.1.01 Articoli/Saggi in rivista - Journal Articles/Essays |
File allegato/i alla scheda:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| TCS2019.pdf | publisher's version - versione editoriale | Licenza default Aisberg | Testo non consultabile |
Pubblicazioni consigliate
Copyright © 2022