{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T11:40:32Z","timestamp":1704368432773},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,5,19]],"date-time":"2010-05-19T00:00:00Z","timestamp":1274227200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00446-010-0105-5","type":"journal-article","created":{"date-parts":[[2010,5,18]],"date-time":"2010-05-18T15:44:55Z","timestamp":1274197495000},"page":"151-161","source":"Crossref","is-referenced-by-count":5,"title":["On the complexity of distributed stable matching with small messages"],"prefix":"10.1007","volume":"23","author":[{"given":"Alex","family":"Kipnis","sequence":"first","affiliation":[]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,5,19]]},"reference":[{"issue":"4","key":"105_CR1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch B.: Complexity of network synchronization. J. ACM. 32(4), 804\u2013823 (1985)","journal-title":"J. ACM."},{"issue":"6","key":"105_CR2","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1109\/49.772430","volume":"17","author":"S.-T. Chuang","year":"1999","unstructured":"Chuang S.-T., Goel A., McKeown N., Prabhakar B.: Matching output queueing with a combined input output queued switch. IEEE J. Sel. Areas Commun. 17(6), 1030\u20131039 (1999)","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"2","key":"105_CR3","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M. Elkin","year":"2006","unstructured":"Elkin M.: An unconditional lower bound on the time-approximation tradeoff for the minimum spanning tree problem. SIAM J. Comput. 36(2), 463\u2013501 (2006)","journal-title":"SIAM J. Comput."},{"key":"105_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."},{"key":"105_CR5","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, MA, USA (1989)"},{"key":"105_CR6","unstructured":"Halld\u00f3rsson, M.M., Irving, R., Iwama, K., Manlove, D. (eds.): MATCH-UP: Matching Under Preferences Reykjavk, Iceland, March 2008. In: Satellite workshop of ICALP 2008. http:\/\/www.dcs.gla.ac.uk\/research\/algorithms\/workshop\/ (2008)"},{"key":"105_CR7","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Morita, Y.: Inapproximability results on stable marriage problems. In: LATIN \u201902: Proc. 5th Latin American Symp. on Theoretical Informatics, pp. 554\u2013568. Springer, London, UK (2002)","DOI":"10.1007\/3-540-45995-2_48"},{"key":"105_CR8","unstructured":"Irving, R.W.: Man-exchange stable marriage. University of Glasgow, Computing Science Department Research Report TR-2004-177 (2004)"},{"key":"105_CR9","doi-asserted-by":"crossref","unstructured":"Irving, R.W., Manlove, D.F., Scott, S.: The hospitals\/residents problem with ties. In: Proc. SWAT 2000 LNCS 1851, pp. 259\u2013271(2000)","DOI":"10.1007\/3-540-44985-X_24"},{"key":"105_CR10","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S.: A survey of the stable marriage problem and its variants. Informatics Education and Research for Knowledge-Circulating Society, 2008. ICKS 2008. In: International Conference on, pp. 131\u2013136 (2008)","DOI":"10.1109\/ICKS.2008.7"},{"key":"105_CR11","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. 17th Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 980\u2013989. ACM, New York, NY, USA (2006)","DOI":"10.1145\/1109557.1109666"},{"issue":"1","key":"105_CR12","first-page":"19","volume":"7","author":"E. Kujansuu","year":"1999","unstructured":"Kujansuu E., Lindberg T., M\u00e4kinen E.: The stable roommates problem and chess tournament pairings. Divulgaciones Matem\u00e1ticas 7(1), 19\u201328 (1999)","journal-title":"Divulgaciones Matem\u00e1ticas"},{"issue":"6","key":"105_CR13","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s00446-005-0127-6","volume":"18","author":"Z. Lotker","year":"2006","unstructured":"Lotker Z., Patt-Shamir B., Peleg D.: Distributed MST for constant diameter graphs. Distrib. Comput. 18(6), 453\u2013460 (2006)","journal-title":"Distrib. Comput."},{"key":"105_CR14","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Pettie, B.: Improved distributed approximate matching. In: Proc. ACM Symposium on Parallellism in Algorithms and Architecture, pp. 129\u2013136. ACM, New York, NY, USA (2008)","DOI":"10.1145\/1378533.1378558"},{"key":"105_CR15","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)"},{"key":"105_CR16","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D. Peleg","year":"2000","unstructured":"Peleg D., Rubinovich V.: Near-tight lower bound on the time complexity of distributed MST construction. SIAM J. Comput. 30, 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0105-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0105-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0105-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:43Z","timestamp":1559136403000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0105-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,19]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["105"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0105-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,19]]}}}