A note on the traveling repairman problem
Alfredo Garcı́a, P. Jodrá, Javier Tejel · Networks · 2002
Abstract 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 Θ(N2) 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. © 2002 Wiley Periodicals, Inc.