ダウンロード数: 89
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-030-48966-3_23.pdf | 130.02 kB | Adobe PDF | 見る/開く |
タイトル: | Strongly Stable and Maximum Weakly Stable Noncrossing Matchings |
著者: | Hamada, Koki Miyazaki, Shuichi https://orcid.org/0000-0003-0369-1970 (unconfirmed) Okamoto, Kazuya |
著者名の別形: | 濱田, 浩気 宮崎, 修一 岡本, 和也 |
キーワード: | Stable marriage Noncrossing matching Polynomial-time algorithms NP-completeness |
発行日: | 2020 |
出版者: | Springer Nature |
誌名: | Lecture Notes in Computer Science |
巻: | 12126 |
開始ページ: | 304 |
終了ページ: | 315 |
抄録: | In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n²) -time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. |
記述: | 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020. |
著作権等: | This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-48966-3_23. The full-text file will be made open to the public on 29 May 2021 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/252798 |
DOI(出版社版): | 10.1007/978-3-030-48966-3_23 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。