کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436754 | 690032 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Parameterized complexity of k-Chinese Postman Problem Parameterized complexity of k-Chinese Postman Problem](/preview/png/436754.png)
We consider the following problem called the k-Chinese Postman Problem (k-CPP): given a connected edge-weighted graph G and integers p and k, decide whether there are at least k closed walks such that every edge of G is contained in at least one of them and the total weight of the edges in the walks is at most p? The problem k-CPP is NP-complete, and van Bevern et al. [4] and Sorge [14] asked whether the k-CPP is fixed-parameter tractable when parameterized by k. We prove that the k -CPP is indeed fixed-parameter tractable. In fact, we prove a stronger result: the problem admits a kernel with O(k2logk) vertices. We prove that the directed version of k-CPP is NP-complete and ask whether the directed version is fixed-parameter tractable when parameterized by k.
Journal: Theoretical Computer Science - Volume 513, 18 November 2013, Pages 124–128