• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

Covering with Clubs: Complexity and Approximability

Dondi, Riccardo; Mauri, Giancarlo; Sikora, Florian; Zoppis, Italo (2018), Covering with Clubs: Complexity and Approximability, dans Iliopoulos, Costas; Wai Leong, Hon; Sung, Wing-Kin, Combinatorial Algorithms, Springer International Publishing : Cham, p. 153-164. 10.1007/978-3-319-94667-2_13

Voir/Ouvrir
155315696970428.pdf (231.5Kb)
Type
Communication / Conférence
Date
2018
Titre du colloque
29th International Workshop on Combinatorial Algorithms (IWOCA 2018)
Date du colloque
2018-07
Ville du colloque
Singapore
Pays du colloque
Singapore
Titre de l'ouvrage
Combinatorial Algorithms
Auteurs de l’ouvrage
Iliopoulos, Costas; Wai Leong, Hon; Sung, Wing-Kin
Éditeur
Springer International Publishing
Ville d’édition
Cham
Isbn
978-3-319-94666-5; 978-3-319-94667-2
Nombre de pages
388
Pages
153-164
Identifiant publication
10.1007/978-3-319-94667-2_13
Métadonnées
Afficher la notice complète
Auteur(s)
Dondi, Riccardo
Università degli Studi di Bergamo
Mauri, Giancarlo
Università degli Studi di Milano-Bicocca [Milano] [UNIMIB]
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Zoppis, Italo
Università degli Studi di Milano-Bicocca [Milano] [UNIMIB]
Résumé (EN)
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.
Mots-clés
approximation algorithms; combinatorial optimization; graph algorithms

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Covering a Graph with Clubs 
    Dondi, Riccardo; Mauri, Giancarlo; Sikora, Florian; Italo, Zoppis (2019) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Parameterized Complexity and Approximation Issues for the Colorful Components Problems 
    Dondi, Riccardo; Sikora, Florian (2016) Communication / Conférence
  • Vignette de prévisualisation
    Parameterized complexity and approximation issues for the colorful components problems 
    Dondi, Riccardo; Sikora, Florian (2018) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis 
    Dondi, Riccardo; Sikora, Florian (2016) Communication / Conférence
  • Vignette de prévisualisation
    The Longest Run Subsequence Problem: Further Complexity Results 
    Sikora, Florian; Dondi, Riccardo (2021) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo