A note on the traveling repairman problem

Given a finite set of N nodes and the time required for traveling among nodes, in the traveling repairman problem, we seek a route that minimizes the sums of the delays for reaching each node. In this note, we present a linear algorithm for solving the traveling repairman problem when the underlying graph is a path, improving the (N²) time and space complexity of the previously best algorithm for this problem. We also provide a linear algorithm for solving the walk problem with deadlines (WPD) on paths.