完全2分木のトーラスへの辺負荷最小埋め込み
スポンサーリンク
概要
- 論文の詳細を見る
本稿では完全2分木を2次元トーラスに最小辺負荷で埋め込む問題を考える. N=2^n-1 (n:偶数) に対して, N点完全2分木はN+1点正方トーラスに辺負荷2, N+2√<N+1>+2点正方トーラスに辺負荷1でそれぞれ埋め込めることが知られている. 我々はこれらの事実より強い結果として, N点完全2分木がN+1点正方トーラスに辺負荷1で埋め込めることを示す. ここで提案する埋め込みは, 辺負荷の下界と正方トーラスの点数に関する下界をともに達成するという意味で最適である.
- 社団法人電子情報通信学会の論文
- 1997-11-27