{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T11:10:22Z","timestamp":1782817822134,"version":"3.54.5"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,5,23]],"date-time":"2009-05-23T00:00:00Z","timestamp":1243036800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00453-009-9326-z","type":"journal-article","created":{"date-parts":[[2009,5,22]],"date-time":"2009-05-22T09:24:26Z","timestamp":1242984266000},"page":"170-187","source":"Crossref","is-referenced-by-count":34,"title":["Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties"],"prefix":"10.1007","volume":"58","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,5,23]]},"reference":[{"key":"9326_CR1","volume-title":"Local Search in Combinatorial Optimization","year":"1997","unstructured":"Aarts, E.H.L., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. Wiley, New York (1997)"},{"key":"9326_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9326_CR3","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9326_CR4","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"issue":"1","key":"9326_CR5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","volume":"16","author":"D. Gusfield","year":"1987","unstructured":"Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1), 111\u2013128 (1987)","journal-title":"SIAM J. Comput."},{"key":"9326_CR6","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D. Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"issue":"1\u20133","key":"9326_CR7","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0304-3975(03)00321-9","volume":"306","author":"M.M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M.M., Irving, R.W., Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y., Scott, S.: Approximability results for stable marriage problems with ties. Theor. Comput. Sci. 306(1\u20133), 431\u2013447 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9326_CR8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"R.W. Irving","year":"1994","unstructured":"Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48(3), 261\u2013272 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9326_CR9","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","volume":"16","author":"R.W. Irving","year":"2008","unstructured":"Irving, R.W., Manlove, D.F.: Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems. J. Comb. Optim. 16(3), 279\u2013292 (2008). doi: 10.1007\/s10878-007-9133-x","journal-title":"J. Comb. Optim."},{"issue":"3","key":"9326_CR10","first-page":"532","volume":"34","author":"R.W. Irving","year":"1987","unstructured":"Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the \u201coptimal\u201d stable marriage. J.\u00a0ACM 34(3), 532\u2013543 (1987)","journal-title":"J.\u00a0ACM"},{"key":"9326_CR11","series-title":"LNCS","first-page":"443","volume-title":"ICALP\u201999","author":"K. Iwama","year":"1999","unstructured":"Iwama, K., Manlove, D., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: ICALP\u201999. LNCS, vol. 1644, pp. 443\u2013452. Springer, Berlin (1999)"},{"issue":"2","key":"9326_CR12","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1137\/S0097539799363359","volume":"32","author":"S. Khuller","year":"2003","unstructured":"Khuller, S., Bhatia, R., Pless, R.: On local search and placement of meters in networks. SIAM J. Comput. 32(2), 470\u2013487 (2003)","journal-title":"SIAM J. Comput."},{"key":"9326_CR13","series-title":"LNCS","first-page":"623","volume-title":"ESA 2008","author":"Z. Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, Z.: Better and simpler approximation algorithms for the stable marriage problem. In: ESA 2008. LNCS, vol. 5193, pp. 623\u2013634. Springer, Berlin (2008)"},{"key":"9326_CR14","series-title":"LNCS","first-page":"662","volume-title":"ICALP 2008","author":"A. Krokhin","year":"2008","unstructured":"Krokhin, A., Marx, D.: On the hardness of losing weight. In: ICALP 2008. LNCS, vol. 5125, pp.\u00a0662\u2013673. Springer, Berlin (2008)"},{"issue":"1\u20132","key":"9326_CR15","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"D.F. Manlove","year":"2002","unstructured":"Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theor. Comput. Sci. 276(1\u20132), 261\u2013279 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9326_CR16","first-page":"7","volume":"3","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Local search. Parameterized Complexity News 3, 7\u20138 (2008)","journal-title":"Parameterized Complexity News"},{"issue":"1","key":"9326_CR17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"issue":"1","key":"9326_CR18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.orl.2007.02.008","volume":"36","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1), 31\u201336 (2008)","journal-title":"Oper. Res. Lett."},{"key":"9326_CR19","unstructured":"Marx, D., Schlotter, I.: Stable assignment with couples: parameterized complexity and local search. Manuscript"},{"key":"9326_CR20","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9326_CR21","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"A.E. Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92, 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"9326_CR22","doi-asserted-by":"crossref","DOI":"10.1017\/CCOL052139015X","volume-title":"Two Sided Matching: A Study in Game-Theoretic Modelling and Analysis","author":"A.E. Roth","year":"1990","unstructured":"Roth, A.E., Sotomayor, M.: Two Sided Matching: A Study in Game-Theoretic Modelling and Analysis. Cambridge University Press, Cambridge (1990)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9326-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9326-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9326-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:04Z","timestamp":1559123104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9326-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,23]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["9326"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9326-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,23]]}}}