Name
Title | ||
|---|---|---|
On the Size of the Zero-Suppressed Binary Decision Diagram that Represents All the Subtrees in a Tree. |
Abstract | ||
|---|---|---|
This paper presents a method of constructing a ZDD that represents all connected subtrees in the given tree and analyzes the size of the resulting ZDD. We show that the size of the ZDD is bounded by O(nh) for a tree with n-nodes and h-height. Furthermore, by properly ordering the ZDD variables, we can further reduce the size to O(n log n), which is surprisingly small compared to represent at most O(2(n)) subtrees. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13186-3_45 | Lecture Notes in Artificial Intelligence |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Tree rotation,Computer science,T-tree,K-ary tree,Binary tree,Left-child right-sibling binary tree,Random binary tree,Interval tree,Search tree | Conference | 8643 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.36 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Norihito Yasuda | 1 | 3 | 1.78 |
| Masaaki Nishino | 2 | 2 | 1.07 |
| Shin-ichi Minato | 3 | 725 | 84.72 |