2分木のハイパキューブへの埋込みについて
スポンサーリンク
概要
- 論文の詳細を見る
任意のN点からなる2分木は「log N」次元キューブにたかだか2の遅延で埋め込むことができると予想されている.任意のN点からなる2分木は「log N」次元キューブにたかだか8の遅延で埋め込めることが知られているが, 上の予想が成立することが確かめられているのは, 完全2分木やパス幅の小さいある種の2分木などの非常に限られた2分木にすぎない.本論文では, これらの結果の自然な一般化を示し, より広い種類の2分木に対して上の予想が成立することを確かめる.すなわち, 2^n点からなり, 足の長さが2以下である均衡した2分キャタピラはn次元キューブに遅延1で埋め込めること, およびN点からなり, 真のパス幅が2以下である2分木は「log N」次元キューブに遅延2で埋め込めることを示す.
- 社団法人電子情報通信学会の論文
- 1998-04-25
著者
関連論文
- 3-連結グラフの3分割アルゴリズム
- 3-連結グラフの3分割アルゴリズム
- Bandwidth of Convex Bipartite Graphs and Related Graph Classes
- A-1-31 On the Three-Dimensional Orthogonal Face Routing
- On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract (Computational Geometry and Discrete Mathematics)
- dcBruijnグラフのVLSI分解について
- deBruijnグラフのVLSI分解について
- 逐次的モジュール配置改善を伴うデータパス合成
- 逐次的モジュール配置改善を伴うデータパス合成
- グラフ理論とその回路とシステムへの応用に関する研究(グラフ,ペトリネット,ニューラルネット及び一般)