| 講演名 | 1998/12/10 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法 畔上 謙吾, 高橋 篤司, 梶谷 洋司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 最大フロー最小カット定理を応用した, 与えられた回路のモデルグラフの最小カットに属す枝を多項式計算時間で列挙し, 最小カットを効率良く探索する構造を与えるアルゴリズムについて述べる.本方法の特徴は, 無向ハイパーグラフで表現された回路のハイパー技をフロー対称変換によって有向グラフに変換し, この上で有向グラフに新しく開発した前方探索と呼ぶ頂点探索をくりかえすことにある.この結果を応用し, 与えられた回路規模制約のもとで最大回路規模を持つ部分回路を得る手法を示す.これを繰り返し適用することによる回路分割技法を提案する. |
| 抄録(英) | Maxflow mincut theorem based polynomial time computation complexity algorithm for enumerating mincut edges of the graph of the graph modelled logic circuits is described. Our algorithm transforms the given underected hypergraph which shows the target logic circuit into a directed graph. Then, iteratively trverses and clusters the directed graph with out newly developed traversing tule. In this paper, we will give a theorem showing that our algorithm is applicable to any undirected hypergraph when the sources and sinks are given. We will also show an example application in the field of circuit bipartitioning which gives the largest possible subcircuit within the given size constraint. |
| キーワード(和) | 回路分割 / 最大フロー最小カット定理 |
| キーワード(英) | Circuit Partitioning / Maxflow-Mincut theorem |
| 資料番号 | VLD98-116,CPSY98-136 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1998/12/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法 |
| サブタイトル（和） | |
| タイトル（英） | Maxflow based Method for Enumerating Mincut Edges of Graph Modelled Logic Circuit |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 回路分割 / Circuit Partitioning |
| キーワード(2)（和/英） | 最大フロー最小カット定理 / Maxflow-Mincut theorem |
| 第 1 著者 氏名（和/英） | 畔上 謙吾 / Kengo Azegami |
| 第 1 著者 所属（和/英） | 東京工業大学工学部電気・電子工学科 Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech. |
| 第 2 著者 氏名（和/英） | 高橋 篤司 / Atsushi Takahashi |
| 第 2 著者 所属（和/英） | 東京工業大学工学部電気・電子工学科 Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech. |
| 第 3 著者 氏名（和/英） | 梶谷 洋司 / Yoji Kajitani |
| 第 3 著者 所属（和/英） | 東京工業大学工学部電気・電子工学科 Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech. |
| 発表年月日 | 1998/12/10 |
| 資料番号 | VLD98-116,CPSY98-136 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 446 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |