Name
Abstract | ||
|---|---|---|
This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly 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 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1587/transinf.E95.D.763 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
graph algorithm, enumeration, rooted tree, family tree | Discrete mathematics,Combinatorics,Vertex (geometry),Computer science,K-ary tree,Binary tree,Link/cut tree,Tree structure,(a,b)-tree,Gomory–Hu tree,Search tree | Journal |
Volume | Issue | ISSN |
E95D | 3 | 1745-1361 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masanobu Ishikawa | 1 | 0 | 0.34 |
| Katsuhisa Yamanaka | 2 | 60 | 15.73 |
| Yota Otachi | 3 | 161 | 37.16 |
| Shin-ichi Nakano | 4 | 246 | 24.40 |