文献

J-GLOBAL ID：200902271532021788   整理番号：09A0924742

小輻輳をもつ高次元グリッドへの分離器ベースグラフ埋め込み

Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion

著者 (1件)： MATSUBAYASHI Akira (Kanazawa Univ., Kanazawa, JPN)
資料名： IEEE International Symposium on Circuits and Systems  (IEEE International Symposium on Circuits and Systems)
巻： 2009 Vol.5  ページ： 2938-2941  発行年： 2009年 
JST資料番号： A0757A  ISSN： 0271-4302  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフ埋め込み問題は,一定制約あるいは最適化基準によりゲストグラフをホストグラフに埋め込むことである。ハイパーキューブにおける分離器ベースグラフ埋め込みでは,最大ノード度Δおよび多重対数関数サイズがlogN次元キューブに埋め込み可能であることが報告されている。本論文では,最適サイズグリッドへの分離器ベース埋め込みにつき報告した。これは二次元グリッドへの埋め込みを一般化したものである。本報告における主要定理を以下に示した。定理1:最大ノード度ΔをもつNノード平面グラフは,O(例d=2の場合Δ²logN)の端部輻輳をもつNノードd次元グリッドに埋め込むことができる。定理2:ツリー幅O(1)をもつNノード,度Δグラフは,O(dN^1/d)の拡大およびO(d²Δ)の端部輻輳をもつNノードd次元グリッド(d≧2)に埋め込むことができる。

シソーラス用語： *輻輳制御 ,  *高次元 ,  格子 ,  分離装置 ,  *埋込み【挿入】 ,  図式解法 ,  ノード法
準シソーラス用語： *グラフ手法 ,  *グリッド方式 ,  ノード計算法 ,  分離器

分類 (2件)： 回路理論一般  (NA02010M) ,  電子回路一般  (NC05010N)

タイトルに関連する用語 (6件)： 輻輳 ,  高次元 ,  グリッド ,  分離器 ,  グラフ ,  埋め込み