| Item type |
学術雑誌論文 / Journal Article(1) |
| 公開日 |
2012-10-03 |
| タイトル |
|
|
タイトル |
Enumerating All Rooted Trees Including k Leaves |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
graph algorithm |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
enumeration |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
rooted tree |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
family tree |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者 |
石川, 雅信
山中, 克久
大舘, 陽太
中野, 眞一
|
| 著者別名 |
|
|
|
識別子Scheme |
WEKO |
|
|
識別子 |
62879 |
|
|
姓名 |
ISHIKAWA, Masanobu |
| 著者別名 |
|
|
|
識別子Scheme |
WEKO |
|
|
識別子 |
62880 |
|
|
姓名 |
YAMANAKA, Katsuhisa |
| 著者別名 |
|
|
|
識別子Scheme |
WEKO |
|
|
識別子 |
62881 |
|
|
姓名 |
OTACHI, Yota |
| 著者別名 |
|
|
|
識別子Scheme |
WEKO |
|
|
識別子 |
62882 |
|
|
姓名 |
NAKANO, Shin-ichi |
| 著者(機関) |
|
|
値 |
Department of Computer Science, Gunma Univetsity |
| 著者(機関) |
|
|
値 |
Department of Electrical Engineering and Computer Science, Iwate University |
| 著者(機関) |
|
|
値 |
Graduate School of Information Sciences, Tohoku University |
| 登録日 |
|
|
日付 |
2012-10-03 |
| 書誌情報 |
IEICE TRANSACTIONS on Information and Systems
巻 E95-D,
号 3,
p. 763-768,
発行日 2012-03-01
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
0916-8532 |
| Abstract |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 出版者 |
|
|
出版者 |
The Institute of Electronics, Information and Communication Engineers |
| 権利 |
|
|
権利情報 |
copyright(C)2012 IEICE |
| 権利URI |
|
|
権利情報 |
http://search.ieice.org/index.html |
| 著者版フラグ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
itis-ve95-dn3p763-768.pdf (255.8 kB)
