Content deleted Content added
An "international conference" is unlikely to be a journal and (despite what IEEE says) its acronym is unlikely to be lowercased; url redundant with hdl |
m Open access bot: hdl, arxiv added to citation with #oabot. |
||
Line 65:
| publisher = Association for Computing Machinery
| title = Proceedings of the 50th Symposium on Theory of Computing (STOC 2018)
| year = 2018
}}</ref>
Counting the number of stable matchings in a given instance is [[♯P-complete|#P-complete]].<ref>{{cite journal
| last1 = Irving | first1 = Robert W.
Line 88 ⟶ 89:
* This process is repeated until everyone is engaged.
This algorithm is guaranteed to produce a stable marriage for all participants in time <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite conference|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|contribution=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|title=International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008)|publisher=IEEE|isbn=978-0-7695-3128-1|hdl=2433/226940|hdl-access=free}}</ref>
Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women.
| |||