The paper presents a dynamic programming algorithm to the Travelling Repairman Problem (TRP) that solves the k-end tree TRP and the cycle TRP in time O(nk) and (n2), respectively. This result generalizes a previous one obtained by F. Afrati et al. The paper also considers TRP with deadlines. Three problems are discussed: (1) Does there exist a route that satisfies all the deadlines? (2) If a route satisfying all the deadlines does not exist, find the route minimizing the maximum lateness. (3) If there exists a route satisfying all the deadlines, find the route minimizing the sum of the delays. When all points are vertices of a tree with k endpoints or a cycle, two polynomial algorithms are given for problems 1 and 2. A pseudo-polynomial algorithm for problem 3 is given.
