文献

J-GLOBAL ID：201802217254920748   整理番号：18A0704404

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

著者 (2件)： 神保潮 (総合研究大学院大) ,  五島正裕 (国立情報学研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 480(DC2017 89-106)  ページ： 203-208  発行年： 2018年02月28日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： FFを用いた回路をラッチを用いた回路に変換する問題は,最小カット問題の一種に帰着する。ただしこの際,始点から終点に至るすべての道にカット・エッジをただ1つ含むという制約がある。そこで我々は,逆方向カット・エッジのない最小カットを見つけるアルゴリズムを提案した。これは容量∞の逆平行エッジを追加したうえで,既存の最大フロー・アルゴリズムを適用するというものであった。しかし,最大フロー・アルゴリズムが∞の容量を扱えるかどうかは自明ではない。本稿では,この容量を有限の値に変更する改良を提案する。これにより,一般の最大フロー・アルゴリズムの利用が可能となる。(著者抄録)

シソーラス用語： 逆方向 ,  端部 ,  *アルゴリズム ,  *回路 ,  ラッチ回路 ,  双安定回路 ,  *最大流問題 ,  グラフ理論
準シソーラス用語： エッジ ,  フリップフロップ ,  *最大フロー問題

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (10件)：

• Harris, D.: Skew-Tolerant Circuit Design, Morgan Kaufmann Publishers (2001).
• Jimbo, U., Yamada, J., Shioya, R. and Goshima, M.: Applying Razor Flip-Flops to SRAM Read Circuits, IEICE Trans. Electron., Vol. E100-C, No. 3, pp. 245-258 (online), DOI: 10.1587/transele.E100.C.245 (2017).
• 神保 潮,山田淳二,五島正裕:動的タイム・ボローイングを可能にするクロッキング方式の適用(2017). cross-disciplinary Workshop on Computing Systems, Infrastructures, and Programming(xSIG 2017)に採択.
• 神保 潮,山田淳二,五島正裕:動的タイム・ボローイングを可能にするクロッキング方式の適用,情報処理学会論文誌:コンピューティングシステム,Vol.10,No.2,pp.1-12(オンライン),入手先〈http://id.nii.ac.jp/1001/00183237/〉(2017).
• 神保 潮,五島正裕:逆方向カット・エッジのない最小カットを求めるアルゴリズム,情報処理学会論文誌:コンピューティングシステム,Vol.10,No.4(2017).(採録決定).

タイトルに関連する用語 (2件)： エッジ ,  アルゴリズム