| Title: | THE COMPLEXITY OF THE PK PARTITION PROBLEM AND RELATED PROBLEMS IN BIPARTITE GRAPHS |
| DOI No: | 10.1142/9781860948534_0007 |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 53-57)
|
| Author(s): | J. MONNOT
Université Paris Dauphine, LAMSADE, CNRS UMR 7024, Place du Maréchal de Lattre de Tassigny, 75775 Paris cedex 16, France
S. TOULOUSE
Université Paris 13, LIPN, CNRS UMR 7030, 99 av. J.-B. Clément, 93430 Villetaneuse, France
|
| Abstract: | In this paper, we continue the investigation made in 7 about Pk packing problems, focusing here on their complexity, according to both the constant k and the maximum degree of the input graph: we prove that Pk PARTITION is NP-complete in bipartite graphs for any k ≥ 3 in graphs with maximum degree 3 (and this even if the graph is planar), whereas it becomes polynomial-time computable in graphs with maximum degree 2. The obtained results actually extend to the minimum k-path partition problem and to the maximum Pk packing problem. Moreover, we provide new approximation results for those two problems, when k is worth 3. |
| Full Text: | View full text in PDF format (252KB) |
| TOC: | Back to Table of Contents |
|
|
