• 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

Finding disjoint paths on edge-colored graphs: more tractability results

Dondi, Riccardo; Sikora, Florian (2018), Finding disjoint paths on edge-colored graphs: more tractability results, Journal of Combinatorial Optimization, 36, 4, p. 1315-1332. 10.1007/s10878-017-0238-6

Voir/Ouvrir
155324627752555.pdf (221.0Kb)
Type
Article accepté pour publication ou publié
Date
2018
Nom de la revue
Journal of Combinatorial Optimization
Volume
36
Numéro
4
Éditeur
Springer
Pages
1315-1332
Identifiant publication
10.1007/s10878-017-0238-6
Métadonnées
Afficher la notice complète
Auteur(s)
Dondi, Riccardo
Università degli Studi di Bergamo
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
The problem of finding the maximum number of vertex-disjointuni-color paths in anedge-colored graph (called MaxCDP) has been recently introduced in literature, motivatedby applications in social network analysis. In this paper we investigate how the complexity ofthe problem depends on graph parameters (namely the number of vertices to remove to makethe graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problemwas known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, evenin FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whosegoal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDPis already hard on graphs at distance two from disjoint paths.
Mots-clés
Parameterized complexity; Approximation; Social networks; Edge-colored graphs

Publications associées

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

  • 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
    Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results 
    Benkouar, A.; Manoussakis, Yannis; Paschos, Vangelis; Saad, Rachid (1996) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    On paths, trails and closed trails in edge-colored graphs 
    Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    On s-t paths and trails in edge-colored graphs 
    Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme; Adria, Lyra; Protti, Fabio (2009) Article accepté pour publication ou publié
  • 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