| dc.contributor.author | Dondi, Riccardo | |
| dc.contributor.author | Mauri, Giancarlo | |
| dc.contributor.author | Sikora, Florian | |
| 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.person.labIds | 119452 | |
| hal.person.labIds | 60273 | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 60273 | |
| hal.identifier | hal-02074964 | * |
