標題: k-path partitions in trees
作者: Yan, JH
Chang, GJ
Hedetniemi, SM
Hedetniemi, ST
應用數學系
Department of Applied Mathematics
公開日期: 21-十月-1997
摘要: 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.
URI: http://hdl.handle.net/11536/248
ISSN: 0166-218X
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 78
Issue: 1-3
起始頁: 227
結束頁: 233
顯示於類別:期刊論文


文件中的檔案:

  1. A1997YC69500017.pdf