Hardness results on the man-exchange stable marriage problem with short preference lists |
| |
| Authors: | Eric Mc Dermid Ichiro Suzuki |
| |
| Affiliation: | University of Wisconsin-Milwaukee, Milwaukee, WI 53211, USA |
| |
| Abstract: | We present two hardness results on the man-exchange stable marriage problem, one of which settles a recent conjecture of Irving on the complexity of determining whether a given instance of the stable marriage problem with short preference lists has a man-exchange stable matching. |
| |
| Keywords: | Stable marriage Man-exchange stable NP-complete Combinatorial problems |
| 本文献已被 ScienceDirect 等数据库收录！ |
