{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T21:05:08Z","timestamp":1774127108394,"version":"3.50.1"},"reference-count":23,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2002,4,1]],"date-time":"2002-04-01T00:00:00Z","timestamp":1017619200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4125,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,4]]},"DOI":"10.1016\/s0304-3975(01)00206-7","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T19:44:18Z","timestamp":1027626258000},"page":"261-279","source":"Crossref","is-referenced-by-count":209,"title":["Hard variants of stable marriage"],"prefix":"10.1016","volume":"276","author":[{"given":"David F","family":"Manlove","sequence":"first","affiliation":[]},{"given":"Robert W","family":"Irving","sequence":"additional","affiliation":[]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[]},{"given":"Yasufumi","family":"Morita","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00206-7_BIB1","unstructured":"Canadian Resident Matching Service, How the matching algorithm works, Web document available at http:\/\/www.carms.ca\/algorith.htm."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(92)90048-N","article-title":"A new fixed point approach for stable networks and stable marriages","volume":"45","author":"Feder","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB3","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB4","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","article-title":"Some remarks on the stable matching problem","volume":"11","author":"Gale","year":"1985","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/S0304-3975(01)00206-7_BIB5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","article-title":"Three fast algorithms for four problems in stable marriage","volume":"16","author":"Gusfield","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB6","series-title":"The Stable Marriage Problem: Structure and Algorithms","author":"Gusfield","year":"1989"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB7","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0406030","article-title":"Minimum edge dominating sets","volume":"6","author":"Horton","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB8","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","article-title":"An efficient algorithm for the \u201cstable roommates\u201d problem","volume":"6","author":"Irving","year":"1985","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB9","unstructured":"R.W. Irving, On the stable room-mates problem, Tech. Report CSC\/86\/R5 University of Glasgow, Department of Computing Science, 1986."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","article-title":"Stable marriage and indifference","volume":"48","author":"Irving","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB11","first-page":"381","article-title":"Matching medical students to pairs of hospitals: a new variation on an old theme","volume":"vol. 1461","author":"Irving","year":"1998"},{"issue":"3","key":"10.1016\/S0304-3975(01)00206-7_BIB12","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/28869.28871","article-title":"An efficient algorithm for the \u201coptimal\u201d stable marriage","volume":"34","author":"Irving","year":"1987","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB13","first-page":"259","article-title":"The Hospitals\/Residents problem with Ties","volume":"vol. 1851","author":"Irving","year":"2000"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB14","first-page":"443","article-title":"Stable marriage with incomplete lists and ties","volume":"vol. 1644","author":"Iwama","year":"1999"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB15","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997. (English translation of Marriages Stables, Les Presses de L'Universit\u00e9 de Montr\u00e9al, 1976).","DOI":"10.1090\/crmp\/010"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB16","unstructured":"G.M. Low, Matching medical students to hospital posts in the West of Scotland, Master's Thesis, University of Glasgow, Department of Computing Science, 1997."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB17","unstructured":"D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, Y. Morita, Hard variants of stable marriage, Tech. Report TR-1999-43, University of Glasgow, Department of Computing Science, September 1999."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB18","unstructured":"E. Ronn, On the complexity of stable matchings with and without ties, Ph.D. Thesis, Yale University, 1986."},{"key":"10.1016\/S0304-3975(01)00206-7_BIB19","doi-asserted-by":"crossref","unstructured":"E. Ronn, NP-complete stable matching problemsJ. Algorithms (11) 1990.","DOI":"10.1016\/0196-6774(90)90007-2"},{"issue":"6","key":"10.1016\/S0304-3975(01)00206-7_BIB20","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","article-title":"The evolution of the labor market for medical interns and residents: a case study in game theory","volume":"92","author":"Roth","year":"1984","journal-title":"J. Political Economy"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB21","doi-asserted-by":"crossref","first-page":"425","DOI":"10.2307\/1913160","article-title":"On the allocation of residents to rural hospitals: a general property of two-sided matching markets","volume":"54","author":"Roth","year":"1986","journal-title":"Econometrica"},{"key":"10.1016\/S0304-3975(01)00206-7_BIB22","series-title":"Two-sided matching: a study in game-theoretic modeling and analysis, Econometric Society Monographs, vol. 18","author":"Roth","year":"1990"},{"issue":"1","key":"10.1016\/S0304-3975(01)00206-7_BIB23","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","article-title":"Edge dominating sets in graphs","volume":"18","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl. Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501002067?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501002067?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,15]],"date-time":"2020-01-15T14:11:35Z","timestamp":1579097495000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501002067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,4]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2002,4]]}},"alternative-id":["S0304397501002067"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00206-7","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,4]]}}}