Show simple item record

The complexity of the Pk partition problem and related problems in bipartite graphs

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-24T09:58:15Z
dc.date.available2011-03-24T09:58:15Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5812
dc.language.isoenen
dc.subjectapproximation algorithmsen
dc.subjectNP-completenessen
dc.subjectbipartite graphsen
dc.subjectminimum k-path partitionen
dc.subjectmaximum (weighted) Pk-packingen
dc.subjectPk-partitionen
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.citationpages53-57en
dc.relation.ispartoftitleINNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005en
dc.relation.ispartofeditorPatnaik, Lalit M.
dc.relation.ispartofeditorTalukder, Asoke K.
dc.relation.ispartofeditorBhattarai, Deepak
dc.relation.ispartofeditorJha, Sudan
dc.relation.ispartofeditorPradhan, Hirendra M.
dc.relation.ispartofeditorIyengar, Sitharama
dc.relation.ispartofpublnameImperial College Pressen
dc.relation.ispartofpublcityLondresen
dc.relation.ispartofdate2005
dc.relation.ispartofpages484en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00017258/en/en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn1-86094-827-8en
dc.relation.conftitle3rd Asian Applied Computing Conference (AACC 2005)en
dc.relation.confdate2005-12
dc.relation.confcityKatmandouen
dc.relation.confcountryNépalen


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