標題: Linear k-arboricities on trees
作者: Chang, GJ
Chen, BL
Fu, HL
Huang, KC
應用數學系
Department of Applied Mathematics
關鍵字: linear forest;linear k-forest;linear arboricity;linear k-arboricity;tree;leaf;penultimate vertex;algorithm;NP-complete
公開日期: 15-Jul-2000
摘要: 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 G disjoint sets and that each induces a subgraph whose components are paths of lengths at most k. This paper studies linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm to determine whether a tree T has la(k)(T)less than or equal to m. (C) 2000 Elsevier Science B.V. All rights reserved.
URI: http://hdl.handle.net/11536/30389
ISSN: 0166-218X
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 103
Issue: 1-3
起始頁: 281
結束頁: 287
Appears in Collections:Articles


Files in This Item:

  1. 000087473600018.pdf