Name
Abstract | ||
|---|---|---|
The subtrees and BC-subtrees (subtrees where any two leaves are at even distance apart) have been intensively studied in recent years. Such structures, under special constraints on degrees, have a wide range of applications in many fields. By way of an approach based on generating functions, we present novel recursive algorithms for enumerating various subtrees and BC-subtrees of maximum degree <= k in trees. The algorithms are explained through detailed examples. We also briefly discuss, in trees, the densities of subtrees (resp. BC-subtrees) with maximum degree <= k among all subtrees (resp. BC-subtrees). For a tree of order n, the novelly proposed algorithms have multiple advantages. (1) Novel (k + 2) (resp. (2k + 3)) variable generating functions were introduced to construct the algorithms. (2) The proposed algorithms solved the fast enumerating problem of subtree (resp. BC-subtrees) with maximum degree constraint, and also make the subtree (resp. BC-subtrees) enumerating algorithms proposed by Yan and Yeh [1] (resp. Yang et al. [2]) a special case of ours with k = n - 1. (3) The time complexity of our algorithm for subtree (resp. BC-subtrees) is O (kn) (resp. O(kn(2))), which is much faster than the O(n2) (resp. O(kn(3))) time method based on algorithm proposed in [1] (resp. [2]). (c) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.09.024 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Subtree, BC-subtree, Maximum degree, Generating function | Journal | 892 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yu Yang | 1 | 18 | 3.42 |
| Xiao-xiao Li | 2 | 0 | 0.34 |
| Meng-yuan Jin | 3 | 0 | 0.34 |
| Long Li | 4 | 0 | 0.34 |
| Hua Wang | 5 | 58 | 11.74 |
| Xiao-Dong Zhang | 6 | 19 | 7.31 |