Thumbnail - No thumbnail

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

Monnot, Jérôme; Toulouse, Sophie (2005), The complexity of the Pk partition problem and related problems in bipartite graphs, dans Patnaik, Lalit M.; Talukder, Asoke K.; Bhattarai, Deepak; Jha, Sudan; Pradhan, Hirendra M.; Iyengar, Sitharama, INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005, Imperial College Press : Londres, p. 53-57

Type
Communication / Conférence
Lien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00017258/en/
Date
2005
Titre du colloque
3rd Asian Applied Computing Conference (AACC 2005)
Date du colloque
2005-12
Ville du colloque
Katmandou
Pays du colloque
Népal
Titre de l'ouvrage
INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD Proceedings of the 3rd Asian Applied Computing Conference Kathmandu, Nepal, 10 – 12 December 2005
Auteurs de l’ouvrage
Patnaik, Lalit M.; Talukder, Asoke K.; Bhattarai, Deepak; Jha, Sudan; Pradhan, Hirendra M.; Iyengar, Sitharama
Éditeur
Imperial College Press
Ville d’édition
Londres
Isbn
1-86094-827-8
Nombre de pages
484
Pages
53-57
Métadonnées
Afficher la notice complète
Auteur(s)
Monnot, Jérôme cc
Toulouse, Sophie cc
Résumé (EN)
In 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.
Mots-clés
approximation algorithms; NP-completeness; bipartite graphs; minimum k-path partition; maximum (weighted) Pk-packing; Pk-partition