• 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

Pk partition problem and related problems in bipartite graphs

Monnot, Jérôme; Toulouse, Sophie (2007), Pk partition problem and related problems in bipartite graphs, in Van Leeuwen, Jan; Italiano, Giuseppe; Van der Hoek, Wiebe; Meinel, Christoph; Sack, Harald; Plasil, Franticek, SOFSEM 2007: Theory and Practice of Computer Science 33nd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, Springer : Berlin, p. 422-433. http://dx.doi.org/10.1007/978-3-540-69507-3_36

View/Open
pk_partition.pdf (177.4Kb)
Type
Communication / Conférence
Date
2007
Conference title
33nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM' 07)
Conference date
2007-01
Conference city
Harrachov
Conference country
République tchèque
Book title
SOFSEM 2007: Theory and Practice of Computer Science 33nd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings
Book author
Van Leeuwen, Jan; Italiano, Giuseppe; Van der Hoek, Wiebe; Meinel, Christoph; Sack, Harald; Plasil, Franticek
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4362
Published in
Berlin
ISBN
978-3-540-69506-6
Number of pages
937
Pages
422-433
Publication identifier
http://dx.doi.org/10.1007/978-3-540-69507-3_36
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Toulouse, Sophie cc
Abstract (EN)
In this paper, we continue the investigation proposed in [15] about the approximability of P k partition problems, but focusing here on their complexity. More precisely, we prove that the problem consisting of deciding if a graph of nk vertices has n vertex disjoint simple paths {P 1, ⋯ ,P n } such that each path P i has k vertices is NP-complete, even in bipartite graphs of maximum degree 3. Note that this result also holds when each path P i is chordless in G[V(P i )]. Then, we prove that the optimization version of these problems, denoted by Max P 3 Packing and MaxInduced P 3 Packing, are not in PTAS in bipartite graphs of maximum degree 3. Finally, we propose a 3/2-approximation for Min3-PathPartition in general graphs within O(nm + n 2logn) time and a 1/3 (resp., 1/2)-approximation for MaxW P 3 Packing in general (resp., bipartite) graphs of maximum degree 3 within O(α(n,3n/2)n) (resp., O(n 2logn)) time, where α is the inverse Ackerman’s function and n = |V|, m = |E|.
Subjects / Keywords
approximation algorithms; APX-hardness; NP-completeness; bipartite graphs; minimum k-path partition; maximum (weighted) induced Pk-packing; maximum (weighted) Pk- packing; Induced Pk-partition; Pk-partition

Related items

Showing items related by title and author.

  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Thumbnail
    The path partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2007) Article accepté pour publication ou publié
  • Thumbnail
    A matching-related property of bipartite graphs with applications in signal processing 
    Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; Rios-Solis, Yasmin Agueda (2009) Document de travail / Working paper
  • Thumbnail
    Approximation results for the weighted P4 partition problems 
    Monnot, Jérôme; Toulouse, Sophie (2005) 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