K-PATH PARTITIONS IN TREES

For a fixed positive integer k, the k-path partition problem is to par tition the vertex set of a graph into the smallest number of paths suc h that each path has at most k vertices. The 2-path partition problem is equivalent to the edge-cover problem. This paper presents a linear- time algorithm for the k-path partition problem in trees. The algorith m is applicable to the problem of finding the minimum number of messag e originators necessary to broadcast a message to all vertices in a tr ee network in one or two time units.