Show simple item record

Covering a Graph with Clubs

hal.structure.identifier
dc.contributor.authorDondi, Riccardo
hal.structure.identifierUniversità degli Studi di Milano-Bicocca = University of Milano-Bicocca [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 = University of Milano-Bicocca [UNIMIB]
dc.contributor.authorItalo, Zoppis
dc.date.accessioned2020-02-03T15:19:14Z
dc.date.available2020-02-03T15:19:14Z
dc.date.issued2019
dc.identifier.issn1526-1719
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20520
dc.language.isoenen
dc.subjectgraphsen
dc.subject.ddc005en
dc.titleCovering a Graph with Clubsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenFinding cohesive subgraphs in a network has been investigated in many network mining applications. Several alternative formulations of cohesive subgraph have been proposed, a notable one of them is s-club, which is a subgraph whose diameter is at most s. Here we consider a natural variant of the well-known Minimum Clique Cover problem, where we aim to cover a given graph with the minimum number of s-clubs, instead of cliques. We study the computational and approximation complexity of this problem, when s is equal to 2 or 3. 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.relation.isversionofjnlnameJournal of Graph Algorithms and Applications
dc.relation.isversionofjnlvol23en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2019
dc.relation.isversionofjnlpages271-292en
dc.relation.isversionofdoi10.7155/jgaa.00491en
dc.relation.isversionofjnlpublisherBrown Universityen
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-02-03T14:57:09Z
hal.identifierhal-02465066*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Covering_a_Graph.pdf
Size:
525.1Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record