グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
小さな通信遅延で並列アルゴリズムを並列計算機に効率的に実装する問題は, 並列アルゴリズムを計算グラフで表現し, 並列計算機を計算機グラフで表現することによって, グラフ埋め込み問題として定式化することができる.埋め込みの辺負荷は通信遅延の下界であることが知られている.したがって, 最小辺負荷でグラフを埋め込むことは非常に重要である.これまでに, 木Tと整数mが与えられたとき, Tをm×2格子へ最小辺負荷で埋め込む事ができるかどうかを判定する問題は, 多項式時間で計算可能であることが知られている.小文では, この結果を拡張し, 連結グラフGと整数mが与えられたとき, Gをm×2格子に埋め込むことができるかどうかを判定し, 埋め込み可能ならば, Gをその格子に埋め込む多項式時間アルゴリズムを示す.
- 社団法人電子情報通信学会の論文
- 2005-01-12
著者
関連論文
- リングにおける競合的オンラインデータ移動アルゴリズム
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 3点上の最適なオンラインページ移動
- 2-パス光ネットワークにおける最適波長割り当て
- キャタピラネットワークにおけるパス彩色
- リングネットワークにおけるファイル配置問題について
- グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム
- 3点上のオンラインページ移動問題に対する新しい上下界
- リングネットワークにおけるページ移動について
- 一様ネットワークにおける厳密競合オンラインデータ管理
- 効率的に分割できるグラフの同点数格子への小さい辺負荷を持つ埋め込み
- 定数コストの横断辺を持つ梯子状ネットワークの最適化
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト(グラフ,ペトリネット,ニューラルネット,及び一般)
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト