Covering with Clubs: Complexity and Approximability
hal.structure.identifier | Università degli Studi di Bergamo | |
dc.contributor.author | Dondi, Riccardo | |
hal.structure.identifier | Università degli Studi di Milano-Bicocca [Milano] [UNIMIB] | |
dc.contributor.author | Mauri, Giancarlo | |
hal.structure.identifier | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] | |
dc.contributor.author | Sikora, Florian
HAL ID: 742949 ORCID: 0000-0003-2670-6258 | |
hal.structure.identifier | Università degli Studi di Milano-Bicocca [Milano] [UNIMIB] | |
dc.contributor.author | Zoppis, Italo | |
dc.date.accessioned | 2019-03-21T08:50:12Z | |
dc.date.available | 2019-03-21T08:50:12Z | |
dc.date.issued | 2018 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/18540 | |
dc.description | Lecture Notes in Computer Science book series (LNCS, volume 10979) | en |
dc.language.iso | en | en |
dc.subject | approximation algorithms | en |
dc.subject | combinatorial optimization | en |
dc.subject | graph algorithms | en |
dc.subject.ddc | 511 | en |
dc.title | Covering with Clubs: Complexity and Approximability | en |
dc.type | Communication / Conférence | |
dc.description.abstracten | Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being s-club, which is a subgraph where each vertex is at distance at most s to the others. Here we consider the problem of covering a given graph with the minimum number of s-clubs. We study the computational and approximation complexity of this problem, when s is equal to 2 or 3. First, we show that deciding if there exists a cover of a graph with three 2-clubs is NP-complete, and that deciding if there exists a cover of a graph with two 3-clubs is NP-complete. Then, we consider the approximation complexity of covering a graph with the minimum number of 2-clubs and 3-clubs. We show that, given a graph G=(V,E) to be covered, covering G with the minimum number of 2-clubs is not approximable within factor O(|V|1/2−ε), for any ε>0, and covering G with the minimum number of 3-clubs is not approximable within factor O(|V|1−ε), for any ε>0. On the positive side, we give an approximation algorithm of factor 2|V|1/2log3/2|V| for covering a graph with the minimum number of 2-clubs. | en |
dc.identifier.citationpages | 153-164 | en |
dc.relation.ispartoftitle | Combinatorial Algorithms | en |
dc.relation.ispartofeditor | Iliopoulos, Costas | |
dc.relation.ispartofeditor | Wai Leong, Hon | |
dc.relation.ispartofeditor | Sung, Wing-Kin | |
dc.relation.ispartofpublname | Springer International Publishing | en |
dc.relation.ispartofpublcity | Cham | en |
dc.relation.ispartofdate | 2018 | |
dc.relation.ispartofpages | 388 | en |
dc.relation.ispartofurl | 10.1007/978-3-319-94667-2 | en |
dc.subject.ddclabel | Principes généraux des mathématiques | en |
dc.relation.ispartofisbn | 978-3-319-94666-5; 978-3-319-94667-2 | en |
dc.relation.conftitle | 29th International Workshop on Combinatorial Algorithms (IWOCA 2018) | en |
dc.relation.confdate | 2018-07 | |
dc.relation.confcity | Singapore | en |
dc.relation.confcountry | Singapore | en |
dc.relation.forthcoming | non | en |
dc.identifier.doi | 10.1007/978-3-319-94667-2_13 | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | oui | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.date.updated | 2019-03-21T08:37:05Z | |
hal.identifier | hal-02074964 | * |
hal.version | 1 | * |
hal.update.action | updateFiles | * |
hal.author.function | aut | |
hal.author.function | aut | |
hal.author.function | aut | |
hal.author.function | aut |