k-path partitions in trees

檔案

日期

1997-10-21

期刊名稱

DISCRETE APPLIED MATHEMATICS

摘要

For a fixed positive integer k, the k-path partition problem is to partition the vertex set of a graph into the smallest number of paths such 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 algorithm is applicable to the problem of finding the minimum number of message originators necessary to broadcast a message to all vertices in a tree network in one or two time units.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料