| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-11-27 13:50 整数計画法によるグラフ埋め込みの定式化とLSI配線への応用 ○井上恵介（北陸先端大/学振）・金子峰雄（北陸先端大）  CAS2009-56 CST2009-29 |
|
| 抄録 | （和） | 本稿はグラフ埋め込み問題に対する整数計画を提案している．提案手法を用いることにより，任意のゲストグラフとホストグラフに対して，与えられた制約を満たす最適なグラフ埋め込みが求められる．また，複数の評価関数の下で設計点を探索しながら所望のグラフ埋め込みを求める設計方式を提供することができる．いくつかのグラフに対して提案手法を適用した結果について報告すると共に，この整数計画の応用として集積回路 (Large Scale Integration: LSI) 設計における多端子配線問題に対する整数計画が構成されることが示される． |
| （英） | This paper proposes an integer linear programming (ILP) formulation of the graph embedding problem, which outputs an optimal solution for any pair of guest and host graph. The proposed ILP provides us with a new design style to obtain a desired graph embedding under a variety of metric functions. This paper shows experimental results for several pairs of guest and host graphs, and also shows an ILP formulation of the multi-terminal routing problem in LSI (Large Scale Integration) design as an application of ILP-based graph embedding. | |
| キーワード | （和） | グラフ埋め込み / 整数計画法 / 多端子配線 / / / / / |
| （英） | Graph embedding / Integer Linear Programming (ILP) / Multi-terminal routing / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 300, CAS2009-56, pp. 65-70, 2009年11月. | |
| 資料番号 | CAS2009-56 | |
| 発行日 | 2009-11-19 (CAS, CST) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2009-56 CST2009-29 |
|
| 研究会情報 | |
| 研究会 | MSS CAS |
| 開催期間 | 2009-11-26 - 2009-11-27 |
| 開催地（和） | 名古屋大学 |
| 開催地（英） | Nagoya University |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | CAS |
| 会議コード | 2009-11-CST-CAS |
| 本文の言語 | 日本語 |
| タイトル（和） | 整数計画法によるグラフ埋め込みの定式化とLSI配線への応用 |
| サブタイトル（和） | |
| タイトル（英） | ILP Formulation of Graph Embedding and Its Application to LSI Routing |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ埋め込み / Graph embedding |
| キーワード(2)（和/英） | 整数計画法 / Integer Linear Programming (ILP) |
| キーワード(3)（和/英） | 多端子配線 / Multi-terminal routing |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 井上 恵介 / Keisuke Inoue / イノウエ ケイスケ |
| 第1著者 所属（和/英） | 北陸先端科学技術大学院大学/日本学術振興会特別研究員 (略称： 北陸先端大/学振) Japan Advanced Institute of Science and Technology/Japan Society for the Promotion of Science (JSPS), Research Fellow (略称： JAIST/JSPS) |
| 第2著者 氏名（和/英/ヨミ） | 金子 峰雄 / Mineo Kaneko / カネコ ミネオ |
| 第2著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-11-27 13:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CAS |
| 資料番号 | CAS2009-56, CST2009-29 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.300(CAS), no.301(CST) |
| ページ範囲 | pp.65-70 |
| ページ数 | 6 |
| 発行日 | 2009-11-19 (CAS, CST) |
[研究会発表申込システムのトップページに戻る]