Abstract:
The min-max
k -traveling salesmen problem on a tree (Min-Max
k-TSPT) is an extension of multiple traveling salesmen problem in tree structure. In this paper, Min-Max
k-TSPT, multi-depot Min-Max
k-TSPT and min-max
k -path cover problem on a tree (Min-Max
k-PCPT) were studied. We present pseudo-polynomial exact algorithms for them by bottom-up dynamic programming. Besides, based on the algorithm of multi-depot Min-Max
k-TSPT, we devise pseudo-polynomial exact algorithms solving multi-depot Min-Max
k-PCPT and multi-depot min-max
k -Chinese postmen problem on a tree (multi-depot Min-Max
k-CPPT) for the first time.