Art

J-GLOBAL ID：201702290283154702   Reference number：17A1913768

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

Author (2)： OKAMOTO KAZUYA (京大 医 病院) ,  MIYAZAKI SHUICHI (京大 学術情報メディアセ)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 117  Issue： 301(MSS2017 24-46)  Page： 67-74  Publication year： Nov. 09, 2017 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： *matching (graph) ,  set ,  *decision problem ,  *computational complexity ,  NP complete problem ,  computation theory ,  Time
Semi thesaurus term： polynomial time

JST classification (1)： System and control theory in general  (IA02010H)

Reference (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.

Terms in the title (3)： 希望 ,  リスト ,  マッチング