文献

J-GLOBAL ID：201202294111920894   整理番号：12A1718406

安定マッチング問題用のGale-Shapleyアルゴリズムにおける提案を決定する好みプロファイル

Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems

著者 (2件)： SUKEGAWA Noriyoshi (Univ. of Tsukuba, Graduate School of Systems and Information Engineering, Tsukuba, JPN) ,  YAMAMOTO Yoshitsugu (Univ. of Tsukuba, Fac. of Engineering, Information and Systems, Tsukuba, JPN)
資料名： Japan Journal of Industrial and Applied Mathematics  (Japan Journal of Industrial and Applied Mathematics)
巻： 29  号： 3  ページ： 547-560  発行年： 2012年10月 
JST資料番号： L5671A  ISSN： 0916-7005  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Gale-Shapleyアルゴリズムによって生成された安定マッチングの戦略的操作可能性に関して,最近Kobayashi及びMatsuiは女性の好みプロファイルの存在性問題を考察した。即ち,与えられた男性の好みプロファイルに対してGale-Shapleyアルゴリズムに男性と女性の定められた完全マッチングを生成させる女性の好みプロファイルを検出する問題を考察した。そのアルゴリズムの実行を通して成された提案の集合の導入及び男性と女性の役割の切り換えによってこの問題を再定式化する事によって,筆者らは男性の好みプロファイルの存在性問題を考察した。そして,その問題が有向グラフが根付き木でそれが多項式時間において可解であるかを検査する問題に還元される事を示した。また,筆者らは提案の集合が与えられた時に双方の性の好みプロファイルの存在性問題が多項式時間において可解である事を示した。Copyright 2012 The JJIAM Publishing Committee and Springer Translated from English into Japanese by JST.

シソーラス用語： *安定性 ,  *マッチング ,  *好み ,  *仕様 ,  スパンニング木 ,  マトロイド ,  計算理論 ,  時間 ,  可能性
準シソーラス用語： *Gale-Shapleyアルゴリズム ,  *プロファイル【情報技術】 ,  可解性 ,  多項式時間

分類 (3件)： 数理計画法  (KA03030M) ,  グラフ理論基礎  (IA02020S) ,  数学一般  (AB01000K)

引用文献 (10件)：

• BERGE, C. Graphs and Hypergraphs. 1973
• FUJISHIGE, S. A primal approach to the independent assignment problem. J. Oper. Res. Soc. Jpn. 1977, 20, 1-15
• GABOW, H. N. Efficient algorithms for a family of matroid intersection problems. J. Algorithms. 1984, 5, 80-131
• GALE, D. College admissions and stability of marriage. Am. Math. Monthly. 1962, 69, 9-15
• GUSFIELD, D. The Stable Marriage Problem : Structure and Algorithms. 1989

タイトルに関連する用語 (6件)： マッチング ,  問題 ,  アルゴリズム ,  提案 ,  好み ,  プロファイル