お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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 
ページ数
発行日 2005-01-12 (CAS) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会