Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorToulouse, Sophie
HAL ID: 177689
ORCID: 0000-0002-6689-1008
dc.date.accessioned2011-03-22T08:52:18Z
dc.date.available2011-03-22T08:52:18Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5777
dc.language.isoenen
dc.subjectapproximation algorithmsen
dc.subjectAPX-hardnessen
dc.subjectNP-completenessen
dc.subjectbipartite graphsen
dc.subjectminimum k-path partitionen
dc.subjectmaximum (weighted) induced Pk-packingen
dc.subjectmaximum (weighted) Pk- packingen
dc.subjectInduced Pk-partitionen
dc.subjectPk-partitionen
dc.subject.ddc003en
dc.titlePk partition problem and related problems in bipartite graphsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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|.en
dc.identifier.citationpages422-433en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4362
dc.relation.ispartoftitleSOFSEM 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, Proceedingsen
dc.relation.ispartofeditorVan Leeuwen, Jan
dc.relation.ispartofeditorItaliano, Giuseppe
dc.relation.ispartofeditorVan der Hoek, Wiebe
dc.relation.ispartofeditorMeinel, Christoph
dc.relation.ispartofeditorSack, Harald
dc.relation.ispartofeditorPlasil, Franticek
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2007
dc.relation.ispartofpages937en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-69507-3en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-69506-6en
dc.relation.conftitle33nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM' 07)en
dc.relation.confdate2007-01
dc.relation.confcityHarrachoven
dc.relation.confcountryRépublique tchèqueen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-69507-3_36


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record