WEKO3
アイテム
逆方向カット・エッジのない最小カットを求めるアルゴリズムの改良
https://ipsj.ixsq.nii.ac.jp/records/186409
https://ipsj.ixsq.nii.ac.jp/records/18640918a728ea-b059-4b53-ac6d-116f6913fc42
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2018 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2018-02-28 | |||||||||
タイトル | ||||||||||
タイトル | 逆方向カット・エッジのない最小カットを求めるアルゴリズムの改良 | |||||||||
言語 | ||||||||||
言語 | jpn | |||||||||
キーワード | ||||||||||
主題Scheme | Other | |||||||||
主題 | 機械学習・アルゴリズム | |||||||||
資源タイプ | ||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
資源タイプ | technical report | |||||||||
著者所属 | ||||||||||
総合研究大学院大学複合科学研究科 | ||||||||||
著者所属 | ||||||||||
国立情報学研究所アーキテクチャ科学研究系 | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
School of Multidisciplinary Sciences, SOKENDAI | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
Systems Architecture Research Division, NII | ||||||||||
著者名 |
神保, 潮
× 神保, 潮
× 五島, 正裕
|
|||||||||
論文抄録 | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | FF を用いた回路をラッチを用いた回路に変換する問題は,最小カット問題の一種に帰着する.ただしこの際,始点から終点に至るすべての道にカット ・ エッジをただ 1 つ含むという制約がある.そこで我々は,逆方向カット ・ エッジのない最小カットを見つけるアルゴリズムを提案した.これは容量 1 の逆平行エッジを追加したうえで,既存の最大フロー・アルゴリズムを適用するというものであった.しかし,最大フロー ・ アルゴリズムが 1 の容量を扱えるかどうかは自明ではない.本稿では,この容量を有限の値に変更する改良を提案する.これにより,一般の最大フロー ・ アルゴリズムの利用が可能となる. | |||||||||
書誌レコードID | ||||||||||
収録物識別子タイプ | NCID | |||||||||
収録物識別子 | AN10096105 | |||||||||
書誌情報 |
研究報告システム・アーキテクチャ(ARC) 巻 2018-ARC-230, 号 35, p. 1-6, 発行日 2018-02-28 |
|||||||||
ISSN | ||||||||||
収録物識別子タイプ | ISSN | |||||||||
収録物識別子 | 2188-8574 | |||||||||
Notice | ||||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
出版者 | ||||||||||
言語 | ja | |||||||||
出版者 | 情報処理学会 |