Show simple item record

Covering with Clubs: Complexity and Approximability

hal.structure.identifierUniversità degli Studi di Bergamo
dc.contributor.authorDondi, Riccardo
hal.structure.identifierUniversità degli Studi di Milano-Bicocca [Milano] [UNIMIB]
dc.contributor.authorMauri, Giancarlo
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
hal.structure.identifierUniversità degli Studi di Milano-Bicocca [Milano] [UNIMIB]
dc.contributor.authorZoppis, Italo
dc.date.accessioned2019-03-21T08:50:12Z
dc.date.available2019-03-21T08:50:12Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18540
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 10979)en
dc.language.isoenen
dc.subjectapproximation algorithmsen
dc.subjectcombinatorial optimizationen
dc.subjectgraph algorithmsen
dc.subject.ddc511en
dc.titleCovering with Clubs: Complexity and Approximabilityen
dc.typeCommunication / Conférence
dc.description.abstractenFinding 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.citationpages153-164en
dc.relation.ispartoftitleCombinatorial Algorithmsen
dc.relation.ispartofeditorIliopoulos, Costas
dc.relation.ispartofeditorWai Leong, Hon
dc.relation.ispartofeditorSung, Wing-Kin
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2018
dc.relation.ispartofpages388en
dc.relation.ispartofurl10.1007/978-3-319-94667-2en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-319-94666-5; 978-3-319-94667-2en
dc.relation.conftitle29th International Workshop on Combinatorial Algorithms (IWOCA 2018)en
dc.relation.confdate2018-07
dc.relation.confcitySingaporeen
dc.relation.confcountrySingaporeen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-94667-2_13en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-21T08:37:05Z
hal.identifierhal-02074964*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
155315696970428.pdf
Size:
231.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record