2024-03-29T08:44:26Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001917882018-10-25T01:26:16Z06201:06202:09108:09572
複数希望リスト安定結婚問題に対するNP完全性の改良jpnアルゴリズム・最適化http://id.nii.ac.jp/1001/00191699/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=191788&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of Japan京都大学京都大学岡本, 和也宮崎, 修一与えられた複数の希望リスト集合全てで安定となるマッチングが存在するか否かを問う安定結婚問題を考える。著者らは過去に、(1) 男性の希望リストの長さが2以下であれば多項式時間で解けること、(2) 全ての希望リストが長さ4以下でもNP完全であること、を示していた。本発表では(2)の結果を強め、男性の希望リストが長さ3以下、女性の希望リストが長さ4以下でもNP完全であることを示す。2018年度 情報処理学会関西支部 支部大会 講演論文集20182018-09-211884-197x2018-10-25