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érenceLien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00017258/en/Date
2005Titre du colloque
3rd Asian Applied Computing Conference (AACC 2005)Date du colloque
2005-12Ville du colloque
KatmandouPays du colloque
NépalTitre 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 2005Auteurs 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
484Pages
53-57
Métadonnées
Afficher la notice complèteRé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-partitionPublications associées
Affichage des éléments liés par titre et auteur.
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2007) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2007) Article accepté pour publication ou publié
-
Toulouse, Sophie; Monnot, Jérôme (2007) Chapitre d'ouvrage
-
Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; Rios-Solis, Yasmin Agueda (2009) Document de travail / Working paper