Abstract
In mobile environment, users retrieve information by portable devices. Since the mobile devices usually have limited power, the issue of minimization the data access latency is important. Periodic broadcasts of frequently requested data can thus reduce the traffics in the air and save the powers of the mobile devices. However, users need to wait for the required data to appear on the broadcast channel. It follows the rule “the more time they wait then the more power devices have to consume. Finding the minimum latency tour can thus help us in solving this kind of problem. In this paper we study the variation of the minimum latency problem (MLP) [2]. The MLP is to find a walk tour on the graph G(V,E) with a distance matrix di,j.Where di,j indicate the distance between vi and vj. Let l(vi) is the latency length of vi, defined to be the distance traveled before the first visiting vi. The minimum latency tour is to minimize the . In some message broadcast and scheduling problem [8] the vertex also has latency time and weight. Those problem need to extend the objective function of the minimum latency tour as . The definition is equivalent to the MLP with no edge distance but vertex latency time and vertex weight. We give a linear algorithm for the un-weighted full k-ary tree or k-path graphs, and O(n log n) time for general tree graphs. The time complexity in trees is the same as Adolphson's result; however, the algorithm given here is not only simpler, easier to understand, but also more flexible and thus can be easily extended to other classes of graphs.