葉の個数を指定した順序木の列挙

• Item type: SIG Technical Reports(1)
• 公開日: 2008-09-05
• タイトル: 葉の個数を指定した順序木の列挙
• タイトル / 言語: en
• タイトル: Efficient Enumeration of Ordered Trees with k Leaves
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者名: 大舘陽太; 山中, 克久; 中野, 眞一
• 著者名(英): Yota, Otachi; Katsuhisa, Yamanaka; Shin-ichi, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本文では，ちょうど n 個の点と k 個の葉をもつ順序木を列挙する高速なアルゴリズムを与える．現在最良のアルゴリズムは，そのような木を １ つ当たり O(n-k) 時間で列挙する．これに対し，我々は，最悪でも １ つ当たり O(1) 時間で列挙するアルゴリズムを与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n-k) time for each, while our algorithm generates such trees in O(1) time for each in worst case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 84(2008-AL-119), p. 69-76, 発行日 2008-09-05
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会