• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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

View/Open
155324627752555.pdf (221.0Kb)
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Journal of Combinatorial Optimization
Volume
36
Number
4
Publisher
Springer
Pages
1315-1332
Publication identifier
10.1007/s10878-017-0238-6
Metadata
Show full item record
Author(s)
Dondi, Riccardo

Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (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.
Subjects / Keywords
Parameterized complexity; Approximation; Social networks; Edge-colored graphs

Related items

Showing items related by title and author.

  • Thumbnail
    Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis 
    Dondi, Riccardo; Sikora, Florian (2016) Communication / Conférence
  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    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é
  • Thumbnail
    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
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo