文献

J-GLOBAL ID：201702290283154702   整理番号：17A1913768

希望リストを複数持つ安定マッチング問題

著者 (2件)： 岡本和也 (京大 医 病院) ,  宮崎修一 (京大 学術情報メディアセ)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 301(MSS2017 24-46)  ページ： 67-74  発行年： 2017年11月09日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 安定マッチング問題とは,男性集合,女性集合,各人の希望リストが与えられ,安定なマッチングを求める問題である。本研究では,同じ男女を対象とした希望リスト集合がk個与えられ,k個全ての希望リスト集合で安定なマッチングが存在するか否かを問う判定問題の計算複雑性を考察した。本研究では以下の結果を得た。(1)任意のk≧2に対して,各人の希望リストの長さが4以下に制限されていてもNP完全である。(2)任意のkに対して,男性の希望リストの長さが2以下であれば,女性の希望リストの長さに制限がなくても多項式時間で解くことができる。(3)任意のkに対して,任意の女性の希望リストがk個の集合全てで同じであれば,多項式時間で解くことができる。(著者抄録)

シソーラス用語： *マッチング ,  集合 ,  *決定問題 ,  *計算量 ,  NP完全問題 ,  計算理論 ,  時間
準シソーラス用語： 多項式時間

分類 (1件)： システム・制御理論一般  (IA02010H)

引用文献 (14件)：

• B. Aspvall, M. F. Plass, and R. E. Tarjan, ′′A linear-time algorithm for testing the truth of certain quantified boolean formulas,′′ Information Processing Letters, Vol.8(3), pp.121-123, 1979.
• S. Even, A. Itai, and A. Shamir, ′′On the complexity of the time table and multi-commodity flow problems,′′ SIAM Journal on Computing, Vol.5(4), pp.691-703, 1976.
• D. Gale and L. S. Shapley, ′′College admissions and the stability of marriage,′′ Amer. Math. Monthly, Vol.69, No.1, pp.9-15, 1962.
• D. Gale and M. Sotomayor, ′′Some remarks on the stable matching problem,′′ Discrete Applied Mathematics, Vol.11, Issue 3, pp.223-232, 1985.
• D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Boston, MA, 1989.

タイトルに関連する用語 (3件)： 希望 ,  リスト ,  マッチング