Polynomial time algorithms for some minimum latency problems

Given a graph and an origin, the minimum weighted latency problem looks for a tour starting at the origin and visiting all the vertices so as to minim ize the sum of the latencies of the vertices multiplied by their weights, i n which the latency of a vertex is the distance from the origin to the firs t visit of the vertex on the tour. In this paper, we show that the minimum weighted latency problem on some graphs can be solved in polynomial time by dynamic programming. The dynamic programming algorithm generalizes the pre vious results in the literature and includes some other cases. We also give an O(n(2)) time algorithm for finding the starting vertex to minimize the latency on a path, and an O(n(4)) time algorithm for the minimum latency pr oblem with multiple repairmen on a path. (C) 2000 Elsevier Science B.V. All rights reserved.