Loading...
Please wait, while we are loading the content...
Similar Documents
On the Complexity of the Stable Marriage Problem for Restricted Instance Class (新時代を担う最適化 : モデル化手法と数値計算 : Rims研究集会報告集)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Igarashi, Yu Kuno, Takahito Sano, Y. |
| Copyright Year | 2016 |
| Abstract | The stable marriage problem is a well studied problem on bipartite graphs, and its special class, MAX SMTI (the problem finding a maximum cardinality stable matching with ties and incomplete lists) is known to be NP-hard. In this paper, we show that MAX SMTI is NP-hard even for highly restricted instances, where each person’s preference list includes at most one strict preference. We also show that there is a polynomial time algorithm for solving the problem for a little more restricted class of instances, where each man has at most one strict preference; and if there exists a man who has one strict preference, then he has the unique first choice. |
| Starting Page | 117 |
| Ending Page | 126 |
| Page Count | 10 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/224463/1/1981-11.pdf |
| Alternate Webpage(s) | http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1981-11.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
