講演抄録/キーワード |
講演名 |
2005-01-19 10:45
グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム ○池田智広・松林 昭(金沢大) |
抄録 |
(和) |
小さな通信遅延で並列アルゴリズムを並列計算機に効率的に実装する問題は,並列アルゴリズムを計算グラフで表現し,並列計算機を計算機グラフで表現することによって,グラフ埋め込み問題として定式化することができる.埋め込みの辺負荷は通信遅延の下界であることが知られている.したがって,最小辺負荷でグラフを埋め込むことは非常に重要である.これまでに,木$T$と整数$m$が与えられたとき,$T$を$m\times 2$格子へ最小辺負荷で埋め込む事ができるかどうかを判定する問題は,多項式時間で計算可能であることが知られている.小文では,この結果を拡張し,連結グラフ$G$と整数$m$が与えられたとき,Gを$m\times 2$格子に埋め込むことができるかどうかを判定し,埋め込み可能ならば,$G$をその格子に埋め込む多項式時間アルゴリズムを示す. |
(英) |
The problem of efficiently implementing parallel algorithms into parallel computers can be formulated as the graph embedding problem, which is to embed with minimal communication overhead the computation graph representing a parallel algorithm into the processor interconnection graph representing a parallel computer. It is well-known that the congestion and/or dilation of the embedding are lower bounds of the communication delay. Thus, it is very important to construct an embedding with minimal congestion and/or dilation. It is known that the problem of determining, given a tree $T$ and an integer $m$, whether $T$ is embeddable into an $m \times 2$ grid with minimal congestion can be solved in polynomial time.
In this report, we give a polynomial time algorithm which determines, given a graph $G$ and an integer $m$, whether $G$ is embeddable into an $m \times 2$ grid with minimal congestion, and if so, embeds $G$ into the grid with minimal congestion. |
キーワード |
(和) |
グラフ埋め込み / 辺負荷 / VLSIレイアウト / / / / / |
(英) |
graph embedding / congestion / VLSI layout / / / / / |
文献情報 |
信学技報, vol. 104, no. 555, CAS2004-61, pp. 7-12, 2005年1月. |
資料番号 |
CAS2004-61 |
発行日 |
2005-01-12 (CAS) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|
研究会情報 |
研究会 |
CAS |
開催期間 |
2005-01-19 - 2005-01-21 |
開催地(和) |
金沢大学 |
開催地(英) |
Kanazawa Univ |
テーマ(和) |
一般 |
テーマ(英) |
Circuits and System, etc. |
講演論文情報の詳細 |
申込み研究会 |
CAS |
会議コード |
2005-01-CAS |
本文の言語 |
日本語 |
タイトル(和) |
グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム |
サブタイトル(和) |
|
タイトル(英) |
A Polynomial Time Algorithm for Embedding Graphs into Ladder with Minimum Congestion |
サブタイトル(英) |
|
キーワード(1)(和/英) |
グラフ埋め込み / graph embedding |
キーワード(2)(和/英) |
辺負荷 / congestion |
キーワード(3)(和/英) |
VLSIレイアウト / VLSI layout |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
池田 智広 / Tomohiro Ikeda / イケダ トモヒロ |
第1著者 所属(和/英) |
金沢大学 (略称: 金沢大)
Kanazawa University (略称: Kanazawa Univ.) |
第2著者 氏名(和/英/ヨミ) |
松林 昭 / Akira Matsubayashi / マツバヤシ アキラ |
第2著者 所属(和/英) |
金沢大学 (略称: 金沢大)
Kanazawa University (略称: Kanazawa Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2005-01-19 10:45:00 |
発表時間 |
25分 |
申込先研究会 |
CAS |
資料番号 |
CAS2004-61 |
巻番号(vol) |
vol.104 |
号番号(no) |
no.555 |
ページ範囲 |
pp.7-12 |
ページ数 |
6 |
発行日 |
2005-01-12 (CAS) |
|