|
|||||
|
|
The path partition problem and related problems in bipartite graphs |
|
| Authors: | Jé rô me Monnot,Sophie Toulouse |
| Affiliation: | a CNRS LAMSADE - UMR 7024, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France b LIPN - UMR CNRS 7030, Institut Galilée, Université Paris 13, 99 av. Jean-Baptiste Clément, 93430 Villetaneuse, France |
| Abstract: | We prove that it is NP-complete to decide whether a bipartite graph of maximum degree three on nk vertices can be partitioned into n paths of length k. Finally, we propose some approximation and inapproximation results for several related problems. |
| Keywords: | Pk-Partition Path packing Path partition Bipartite graphs boldFont" >APX-Hardness Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |