標題: 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
顯示於類別:期刊論文