The complexity of the Pk partition problem and related problems in bipartite graphsReportar como inadecuado




The complexity of the Pk partition problem and related problems in bipartite graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision 2 LIPN - Laboratoire d-Informatique de Paris-Nord

Abstract : 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.

Keywords : Pk-partition maximum weighted Pk-packing minimum k-path partition bipartite graphs NP-completeness approximation algorithms





Autor: Jérôme Monnot - Sophie Toulouse -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados