論文

査読有り 最終著者
2018年3月

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

情報処理学会論文誌:コンピューティングシステム
  • 神保 潮
  • ,
  • 五島 正裕

11
1
開始ページ
1
終了ページ
11
記述言語
日本語
掲載種別
研究論文(学術雑誌)

FF を用いた回路をラッチを用いた回路に変換する問題は,最小カット問題の一種に帰着する.ただしこの際,始点から終点に至るすべての道にカット・エッジをただ 1つ含むという制約がある.既存の最小カット・アルゴリズムでは,この制約を満たすことができない.本稿では,この制約が,カットが逆方向カット・エッジを含まないことと等価であることを証明し,逆方向カット・エッジのない最小カットを見つけるアルゴリズムを提案する.このアルゴリズムにおいて最もオーダが大きい部分は既存の最大フロー・アルゴリズムであり,提案アルゴリズム全体のオーダはこれより悪化することはない.実験により,ゲート数 約3.4万,配線数 約9.7万程度の回路に対しても,約375秒の実用的な時間で最適解が求められることが分かった.

リンク情報
URL
http://id.nii.ac.jp/1001/00186635/
ID情報
  • ISSN : 1882-7829

エクスポート
BibTeX RIS