最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法

• Item type: SIG Technical Reports(1)
• 公開日: 1998-12-10
• タイトル: 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
• タイトル / 言語: en
• タイトル: Maxflow based Method for Enumerating Mincut Edges of Graph Modelled Logic Circuit
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学 工学部 電気・電子工学科
• 著者所属: 東京工業大学 工学部 電気・電子工学科
• 著者所属: 東京工業大学 工学部 電気・電子工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者名: 畔上, 謙吾; 高橋, 篤司; 梶谷, 洋司
• 著者名(英): Kengo, Azegami; Atsushi, Takahashi; Yoji, Kajitani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最大フロー最小カット定理を応用した，与えられた回路のモデルグラフの最小カットに属す枝を多項式計算時間で列挙し，最小カットを効率良く探索する構造を与えるアルゴリズムについて述べる．本方法の特徴は，無向ハイパーグラフで表現された回路のハイパー枝をフロー対称変換によって有向グラフに変換し，この上で有向グラフに新しく開発した前方探索と呼ぶ頂点探索をくりかえすことにある．この結果を応用し 与えられた回路規模制約のもとで最大回路規模を持つ部分回路を得る手法を示す．これを繰り返し適用することによる回路分割技法を提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Maxflow mincut theorem based polynomial time computation complexity algorithm for enumerating mincut edges of the graph modelled logic circuits is described. Our algorithm transforms the given undirected hypergraph which shows the target logic circuit into a directed graph. Then, iteratively traverses and clusters the directed graph with our newly developed traversing rule. 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 1998, 号 113(1998-SLDM-090), p. 131-138, 発行日 1998-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会