標題: | Algorithmic aspects of linear k-arboricity |
作者: | Chang, GJ 應用數學系 Department of Applied Mathematics |
關鍵字: | linear forest;linear k-forest;linear arboricity;linear k-arboricity;tree;leaf;penultimate vertex;algorithm;NP-complete |
公開日期: | 1-三月-1999 |
摘要: | For a fixed positive integer k, the linear k-arboricity la(k)(G) of a graph G is the minimum number l such that the edge set E(G) can be partitioned into l disjoint sets, each induces a subgraph whose components are paths of lengths at most k. This paper examines linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm for determining whether a tree T has la(2)(T) less than or equal to m. We also give a characterization for a tree T with maximum degree 2m having la(2)(T) = m. |
URI: | http://hdl.handle.net/11536/31503 |
ISSN: | 1027-5487 |
期刊: | TAIWANESE JOURNAL OF MATHEMATICS |
Volume: | 3 |
Issue: | 1 |
起始頁: | 73 |
結束頁: | 81 |
顯示於類別: | 期刊論文 |