Bodlaender, Hans L.; Yamazaki, Koichi Some results for cluster traveling salesperson problem. (English) Zbl 0945.90044 RIMS Kokyuroku 1054, 32-39 (1998). Summary: In this paper, we consider a generalization on the Travelling Salesperson Problem, called the Cluster Traveling Salesperson Problem (abbreviated CTSP). In CTSP, we are given a graph \(G=(V,E)\) and a partition of \(V:V_1,\dots,V_k\) (the ‘clusters’); the goal is to find an optimum (i.e. shortest) tour which visits at least one city in each cluster. We will show that CTSP with triangle inequality is at least as hard to approximate as Minimum Set Cover. We also give an algorithm that solves \(k\)-CSTP in \(O(2^{3k}\cdot|V|^2)\) time, where \(k\) denotes the number of clusters. MSC: 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 68Q25 Analysis of algorithms and problem complexity Keywords:cluster traveling salesperson problem; minimum set cover PDFBibTeX XMLCite \textit{H. L. Bodlaender} and \textit{K. Yamazaki}, RIMS Kokyuroku 1054, 32--39 (1998; Zbl 0945.90044)