3人部屋安定ルームメイト問題のNP完全性

• Material Type: 文書・図像類
• Title: 3人部屋安定ルームメイト問題のNP完全性
• Author/Editor: 岡本, 和也; 宮崎, 修一; 岩間, 一雄
• Author Heading: 岡本, 和也; 宮崎, 修一; 岩間, 一雄
• Publication, Distribution, etc.: 電子情報通信学会
• Publication Date: 2007-10-09
• Publication Date (W3CDTF): 2007-10-09
• Alternative Title: NP-Completeness of the Stable Roommates Problem with Triple Rooms
• Periodical title: 電子情報通信学会技術研究報告
• No. or year of volume/issue: 107 258
• Volume: 107
• Issue: 258
• Pages: 1-6
• ISSN (Periodical Title): ISSN : 0913-5685
• Text Language Code: jpn
• Subject Heading: 安定マッチング; 安定ルームメイト問題; NP完全; stable matching; the stable roommates problem; NP-complete
• Target Audience: 一般
• Note (General): <コンピュテーション研究会(COMP)> 2007年10月16日(火) 10:40 - 16:40, 東北大学工学部電子情報システム・応物系1号館451・453号室
• Format (IMT): application/pdf
• Source: IEICE_tec.rep_COMP2007-41.pdf （fulltext）; http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/227008/1/IEICE_tec.rep_COMP2007-41.pdf
• Access Restrictions: インターネット公開
• Rights (production): © 電子情報通信学会(IEICE)
• Periodical Title (NCID): AN10013152; https://ci.nii.ac.jp/ncid/AN10013152
• Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• Original Data Provider (Database): 京都大学 : 京都大学学術情報リポジトリ

• Summary, etc.: 安定ルームメイト問題は, 希望リストに基づいて「安定性」を満たすように, 2N人の人間をN組のペアに分割する問題である.安定ルームメイト問題は解を持たない場合もあるが, 解を持つか否かを判定し, 持つ場合には解を見つける多項式時間アルゴリズムが知られている.本研究ではこの問題を拡張し, 3N人の人間...