ダウンロード数: 55
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s00453-021-00832-9.pdf | 3.33 MB | Adobe PDF | 見る/開く |
タイトル: | Strongly Stable and Maximum Weakly Stable Noncrossing Matchings |
著者: | Hamada, Koki Miyazaki, Shuichi Okamoto, Kazuya |
著者名の別形: | 濱田, 浩気 宮崎, 修一 岡本, 和也 |
キーワード: | Stable marriage Noncrossing matching Polynomial-time algorithms NP-completeness |
発行日: | Sep-2021 |
出版者: | Springer Nature |
誌名: | Algorithmica |
巻: | 83 |
号: | 9 |
開始ページ: | 2678 |
終了ページ: | 2696 |
抄録: | 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. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomial time if the length of preference lists of one side is bounded by one (but that of the other side is unbounded). |
著作権等: | © The Author(s) 2021 This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. |
URI: | http://hdl.handle.net/2433/276423 |
DOI(出版社版): | 10.1007/s00453-021-00832-9 |
出現コレクション: | 学術雑誌掲載論文等 |
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス