Article ID Journal Published Year Pages File Type
1143004 Operations Research Letters 2007 8 Pages PDF
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
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The path partition problem and related problems in bipartite graphs
Authors
, ,