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分解について
- 逐次的モジュール配置改善を伴うデータパス合成
- 逐次的モジュール配置改善を伴うデータパス合成
- グラフ理論とその回路とシステムへの応用に関する研究(グラフ,ペトリネット,ニューラルネット及び一般)
- グラフ理論とその回路とシステムへの応用に関する研究(グラフ,ペトリネット,ニューラルネット及び一般)
- シャッフル交換ネットワークとde Bruijnネットワークの3次元VLSIレイアウト
- de Bruijn ネットワークの効率的なレイアウトについて
- 先行制約付きタスクの通信遅延を考慮した効率的スケジューリング
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 完全二分木ATMネットワークにおける最適な仮想パスレイアウト
- 完全二分木ATMネットワークにおける最適な仮想パスレイアウト
- マルチプロセッサシステムの逐次診断について
- 幅制約モジュール配置問題のSAを用いた最適化手法
- 幅制約モジュール配置問題のSAを用いた最適化手法
- 幅制約モジュール配置問題のSAを用いた最適化手法
- 境界制約付配置問題に対するペナルティ関数を用いたSA探索手法
- 境界制約付配置問題に対するペナルティ関数を用いたSA探索手法
- 3次元パッキングに基づく動的再構成スケジューリング
- 3次元パッキングに基づく動的再構成スケジューリング
- 3次元パッキングに基づく動的再構成スケジューリング
- A-1-29 A Necessary Condition for Orthogonal Ray Graphs
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- コスト制限付最小遅延マルチキャスト(信号処理,LSI,及び一般)
- 外平面グラフの直交描画について(グラフ,ペトリ,ニューラルネット,及び一般)
- 外平面グラフの直交描画について(グラフ,ペトリ,ニューラルネット,及び一般)
- 外平面グラフの直交描画について
- 2分木のハイパキューブへの埋込みについて
- パス幅の制限された2分木のパスと格子への効率的な埋め込み
- WSIネットワークの動的耐故障性について
- ネットワークの回線交換固定ルーティングの評価
- トーラスの耐故障固定ルーティングについて
- グラフのトポロジカルバンド幅と真のパス幅
- ハイパーキューブへのスケジューリング
- 逐次診断可能次数の上界
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 耐故障線形配列の最適構成
- 最適な耐故障線形アレイについて
- 最適な耐故障線形アレイについて
- マルチプロセッサシステムに対する適応的故障診断について
- 部分k木ネットワークとバタフライネットワークに対して確率的故障に耐える疎なネットワーク
- 部分k木ネットワークとバタフライネットワークに対して確率的故障に耐える疎なネットワーク
- 資源割り当て駆動スケジューリングにおけるレジスタ間転送の自動挿入(システム設計及び一般)
- 資源割り当て駆動スケジューリングにおけるレジスタ間転送の自動挿入(システム設計及び一般)
- シーケンスペアに基づく配置解空間の効率的なSA探索のための隣接解選択
- シーケンスペアに基づく配置解空間の効率的なSA探索のための隣接解選択
- 大域的配線を考慮したフロアプラン生成のためのグラフ平面化
- 大域的配線を考慮したフロアプラン生成のためのグラフ平面化
- 配線資源を考慮した高位合成
- 配線資源を考慮した高位合成
- マルチプロセッサシステムの逐次診断について
- CCCの逐次診断可能次数の評価
- 光ネットワーク上のオンラインマルチキャスティング
- CCCの3次元空間不変光相互結合による最適実装について
- ピラミッドネットワークの3次元レイアウト
- ピラミッドネットワークの3次元レイアウト
- De Bruijnネットワークの3次元レイアウト
- d値de BruijnグラフのVLSI分解について
- マルチプロセッサシステムの確率的逐次診断について
- WDMネットワークにおけるルーティングと波長変換
- エルモア遅延モデルに基づく最大信号伝播遅延最小化スタイナー配線
- A Note on the Three-Dimensional Optical Implementation of Regular Bipartite Graphs
- 空間不変3次元光結合によるハイパーキューブの最適実現
- CCCの3次元空間不変光相互結合による最適実装について
- CCCの逐次診断可能次数の評価