文献

J-GLOBAL ID：201002222082428408   整理番号：10A1156386

次数限界を持つツリーの一定時間生成

Constant Time Generation of Trees with Degree Bounds

著者 (2件)： ZHUANG Bingbing (Kyoto Univ.) ,  NAGAMOCHI Hiroshi (Kyoto Univ.)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2010  号： 3  ページ： ROMBUNNO.AL-131,NO.8  発行年： 2010年10月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 頂点の数n,直径に対する下界d,容量関数Δ(k)≧2,k=0,1,...,((n/2)の整数部分),が与えられた時,本論文では,根付きツリーTの中心からの距離がkである各頂点の次数が高々Δ(k)となるような正確にn個の頂点および少なくともdの直径を持つすべての根付きツリーTの数え上げ問題を取り上げて考察した。ここでは,最悪ケースでも出力ごとにO(1)時間遅延においてO(n)空間を用いて重複無しにそのようなツリーをすべて生成するアルゴリズムを与えた。(翻訳著者抄録)

シソーラス用語： *木【グラフ】 ,  ジェネレータ ,  時間 ,  *計算機アルゴリズム ,  限界 ,  距離 ,  頂点 ,  直径 ,  *数え上げ理論 ,  *計算量 ,  記憶容量
準シソーラス用語： 一定時間生成 ,  下界 ,  根付きツリー

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 次数 ,  限界