- 著者
-
松林 昭
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. CAS, 回路とシステム (ISSN:09135685)
- 巻号頁・発行日
- vol.104, no.555, pp.19-24, 2005-01-12
グラフを格子に最小の辺負荷で埋め込む問題は, メッセージ交換並列計算機に並列アルゴリズムを効率的に実装する問題等に応用がある.小文では, 効率的に再帰分割可能であるグラフは同じ点数の格子に小さい辺負荷で埋め込めることを示す.特にN点平面グラフがN点格子に辺負荷O(Δ^2logN)で埋め込めること, さらに, グラフが木である場合には辺負荷O(Δ)で埋め込めることを示す.木に対する辺負荷は定数係数の範囲内で最小であり, 平面グラフに対する辺負荷は知られている下界に対してO(min{Δ^2√<logN>, Δlog N})の係数の範囲内で最適である.