逆方向カット・エッジのない最小カットを求めるアルゴリズム

• Item type: Trans(1)
• 公開日: 2018-03-14
• タイトル: 逆方向カット・エッジのない最小カットを求めるアルゴリズム
• タイトル / 言語: en
• タイトル: An Algorithm to Find the Minimum Cut without Backward Cut Edges
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: グラフ・アルゴリズム，最小カット，最大フロー最小カット定理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 総合研究大学院大学複合科学研究科
• 著者所属: 国立情報学研究所アーキテクチャ科学研究系
• 著者所属(英): en
• 著者所属(英): School of Multidisciplinary Sciences, SOKENDAI
• 著者所属(英): en
• 著者所属(英): Systems Architecture Research Division, NII
• 著者名: 神保, 潮; 五島, 正裕
• 著者名(英): Ushio, Jimbo; Masahiro, Goshima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: FFを用いた回路をラッチを用いた回路に変換する問題は，最小カット問題の一種に帰着する．ただしこの際，始点から終点に至るすべての道にカット・エッジをただ1つ含むという制約がある．既存の最小カット・アルゴリズムでは，この制約を満たすことができない．本稿では，この制約が，カットが逆方向カット・エッジを含まないことと等価であることを証明し，逆方向カット・エッジのない最小カットを見つけるアルゴリズムを提案する．このアルゴリズムにおいて最もオーダが大きい部分は既存の最大フロー・アルゴリズムであり，提案アルゴリズム全体のオーダはこれより悪化することはない．実験により，ゲート数約3.4万，配線数約9.7万程度の回路に対しても，約375秒の実用的な時間で最適解が求められることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A problem to convert a circuit with FFs into one with latches leads to a kind of minimum cut problem with a constraint that each of the paths from the start to terminal points has a single cut edge. Existing minimum cut algorithms do not satisfy this constraint. This paper proves that this constraint is equivalent to one that the cut does not have a backward cut edge, and proposes an algorithm to find the minimum cut without backward cut edges. The most complex part of the proposed algorithm is one of existing maximum flow algorithms, and the time-complexity of the whole proposed algorithm is not larger than the maximum flow algorithm used. Experimental results show that the algorithm can practically find the optimal solution for a large circuit with approximately 34 thousand gates and 97 thousand wires in approximately 375 seconds.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 11, 号 1, p. 1-11, 発行日 2018-03-14
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会