IEICE TRANSACTIONS on Information
Enumerating All Rooted Trees Including k Leaves
Summary :
This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.3 pp.763-768
- Publication Date
- 2012/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.763
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masanobu ISHIKAWA, Katsuhisa YAMANAKA, Yota OTACHI, Shin-ichi NAKANO, "Enumerating All Rooted Trees Including k Leaves" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 3, pp. 763-768, March 2012, doi: 10.1587/transinf.E95.D.763.
Abstract: This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.763/_p
Copy
@ARTICLE{e95-d_3_763,
author={Masanobu ISHIKAWA, Katsuhisa YAMANAKA, Yota OTACHI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={Enumerating All Rooted Trees Including k Leaves},
year={2012},
volume={E95-D},
number={3},
pages={763-768},
abstract={This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.},
keywords={},
doi={10.1587/transinf.E95.D.763},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Enumerating All Rooted Trees Including k Leaves
T2 - IEICE TRANSACTIONS on Information
SP - 763
EP - 768
AU - Masanobu ISHIKAWA
AU - Katsuhisa YAMANAKA
AU - Yota OTACHI
AU - Shin-ichi NAKANO
PY - 2012
DO - 10.1587/transinf.E95.D.763
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2012
AB - This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.
ER -
English
