WEKO3
アイテム
2部グラフ上の最適完全マッチングを列挙するアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32744
https://ipsj.ixsq.nii.ac.jp/records/327444feb9174-ede7-48e1-89e1-a04505a0e8c4
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1989 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1989-01-25 | |||||||
タイトル | ||||||||
タイトル | 2部グラフ上の最適完全マッチングを列挙するアルゴリズム | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Finding All Minimum Cost Perfect Matchings in Bipartite Graphs | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東京工業大学理学部情報科学科 | ||||||||
著者所属 | ||||||||
東京工業大学理学部情報科学科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Sciences, Tokyo Institute of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Sciences, Tokyo Institute of Technology | ||||||||
著者名 |
福田, 公明
× 福田, 公明
|
|||||||
著者名(英) |
Komei, Fukuda
× Komei, Fukuda
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | この論文では、割当問題における最適解を全て求めるようなアルゴリズムを提案する。このアルゴリズムは1つの最適解を出力してからもう1つを出力するまでにO(n^3)の手間を必要とし、また用いる記憶容量は全体でO(n^2)となっている。割当問題における全ての最適解を求める問題は、与えられた2部グラフ上の完全マッチングを全て求めるという間題を子問題として含んでおり、このことより本アルゴリズムは完全マッチングの数え上げを行うアルゴリズムと見ることもできる。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The Hungarian method gives an efficient algorithm for finding a minimal cost perfect matching. This paper describes an efficient algorithm for finding all minimal cost perfect matchings. The computational effort required to generate each additional perfect matching is O(n^3). And it requires O(n^2) memory storage. Here we will show that the enumeration of all minimal cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1989, 号 8(1988-AL-005), p. 125-132, 発行日 1989-01-25 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |