a Department of Information and Computer Sciences, Toyohashi University of Technology, Toyohashi, Aichi 441-8580, Japan
b Matsushita Electric Industrial Co., Ltd., Kadoma 1006, Osaka 571-8501, Japan
Abstract:
Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2?2/(p+1))-approximation algorithm which runs in O(pp?1np?1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p?1)!·n) time.