The path partition problem and related problems in bipartite graphs

The path partition problem and related problems in bipartite graphs

0.00 Avg rating—0 Votes
Article ID: iaor20083345
Country: Netherlands
Volume: 35
Issue: 5
Start Page Number: 677
End Page Number: 684
Publication Date: Sep 2007
Journal: Operations Research Letters
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.