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
2007Journal name
Operations Research LettersVolume
35Number
5Publisher
Elsevier
Pages
677-684
Publication identifier
Metadata
Show full item recordAbstract (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 algorithmsRelated items
Showing items related by title and author.
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Toulouse, Sophie (2007) Communication / Conférence
-
Toulouse, Sophie; Monnot, Jérôme (2007) Chapitre d'ouvrage
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence