Thumbnail - Request a copy

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

Type
Article accepté pour publication ou publié
Date
2007
Journal name
Operations Research Letters
Volume
35
Number
5
Publisher
Elsevier
Pages
677-684
Publication identifier
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Toulouse, Sophie cc
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 / Keywords
Pk-Partition; Path packing; Path partition; Bipartite graphs; APX-Hardness; Approximation algorithms