The path partition problem and related problems in bipartite graphs
Monnot, Jérôme; Toulouse, Sophie (2007), The path partition problem and related problems in bipartite graphs, Operations Research Letters, 35, 5, p. 677-684. http://dx.doi.org/10.1016/j.orl.2006.12.004
TypeArticle accepté pour publication ou publié
Journal nameOperations Research Letters
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsPk-Partition; Path packing; Path partition; Bipartite graphs; APX-Hardness; Approximation algorithms
Showing items related by title and author.