کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419242 | 683758 | 2016 | 18 صفحه PDF | دانلود رایگان |
A many-to-many kk-disjoint path cover (kk-DPC for short) of a graph GG joining the pairwise disjoint vertex sets SS and TT, each of size kk, is a collection of kk vertex-disjoint paths between SS and TT, which altogether cover every vertex of GG. This is classified as paired , if each vertex of SS must be joined to a specific vertex of TT, or unpaired, if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining SS and TT given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired kk-DPC problem on a unit interval graph is polynomially solvable for any fixed kk.
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 132–149