Show simple item record

dc.contributor.authorMonnot, Jérôme
dc.contributor.authorToulouse, Sophie
dc.date.accessioned2011-04-18T14:03:20Z
dc.date.available2011-04-18T14:03:20Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5994
dc.language.isoenen
dc.subjectPk-partitionen
dc.subjectmaximum (weighted) Pk-packingen
dc.subjectminimum k-path partitionen
dc.subjectbipartite graphsen
dc.subjectNP-completenessen
dc.subjectapproximation algorithmsen
dc.subject.ddc003en
dc.titleThe complexity of the Pk partition problem and related problems in bipartite graphsen
dc.typeCommunication / Conférence
dc.description.abstractenIn this paper, we continue the investigation made in [MT05] about the approximability of Pk partition problems, but focusing here on their complexity. Precisely, we aim at designing the frontier between polynomial and NP-complete versions of the Pk partition problem in bipartite graphs, according to both the constant k and the maximum degree of the input graph. We actually extend the obtained results to more general classes of problems, namely, the minimum k-path partition problem and the maximum Pk packing problem. Moreover, we propose some simple approximation algorithms for those problems.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.ispartofeditorPlasil, Frantisek
dc.relation.ispartofeditorSack, Harald
dc.relation.ispartofeditorMeinel, Christoph
dc.relation.ispartofeditorVan der Hoek, Wiebe
dc.relation.ispartofeditorItaliano, Giuseppe F.
dc.relation.ispartofeditorVan Leeuwen, Jan
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.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00152314/en/en
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 2007)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

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record