グラフのハイパーキューブへの辺負荷最小の埋め込み

スポンサーリンク

概要

論文の詳細を見る
本稿ではグラフをハイパーキューブに最小の辺負荷で埋め込む問題を考える.任意のN点グラフは,最大次数が6⌈log N⌉以下ならば6⌈log N⌉次元キューブに辺負荷1で埋め込めることが知られている.また,任意のN点2分木は⌈log N⌉次元キューブにO(1)の辺負荷で埋め込めることが知られている.我々は以上の結果を拡張し,以下の定理を示す.●任意のN点グラフは,最大次数が2⌈log N⌉以下ならば2⌈log N⌉次元キューブに辺負荷1で埋め込めむことができる.●任意のN点2分木は,⌈log N⌉次元キューブに辺負荷6で埋め込めむことができる.ここで提案する埋め込みは非常に単純であり,多項式時間で構成できる.
一般社団法人情報処理学会の論文
1994-07-22

著者

関連論文

もっと見る

スポンサーリンク