Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree

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.