{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T06:03:59Z","timestamp":1778911439664,"version":"3.51.4"},"reference-count":10,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            An instance of the stable marriage problem is an undirected bipartite graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>X<\/jats:italic>\n            \u222a\n            <jats:italic>W<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with linearly ordered adjacency lists with ties allowed in the ordering. A matching\n            <jats:italic>M<\/jats:italic>\n            is a set of edges, no two of which share an endpoint. An edge\n            <jats:italic>e<\/jats:italic>\n            = (\n            <jats:italic>a<\/jats:italic>\n            ,\n            <jats:italic>b<\/jats:italic>\n            ) \u2208\n            <jats:italic>E<\/jats:italic>\n            \u2216\n            <jats:italic>M<\/jats:italic>\n            is a\n            <jats:italic>blocking edge<\/jats:italic>\n            for\n            <jats:italic>M<\/jats:italic>\n            if\n            <jats:italic>a<\/jats:italic>\n            is either unmatched or strictly prefers\n            <jats:italic>b<\/jats:italic>\n            to its partner in\n            <jats:italic>M<\/jats:italic>\n            , and\n            <jats:italic>b<\/jats:italic>\n            is unmatched, strictly prefers\n            <jats:italic>a<\/jats:italic>\n            to its partner in\n            <jats:italic>M<\/jats:italic>\n            , or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nm<\/jats:italic>\n            ) algorithm for computing strongly stable matchings, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices and\n            <jats:italic>m<\/jats:italic>\n            the number of edges. The previous best algorithm had running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            \u2211\n            <jats:sub>\n              <jats:italic>h\u2208H<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>h<\/jats:italic>\n            <\/jats:sub>\n            ) algorithm for computing a strongly stable matching in the hospitals-residents problem, where\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>h<\/jats:italic>\n            <\/jats:sub>\n            is the quota of a hospital\n            <jats:italic>h<\/jats:italic>\n            . The previous best algorithm had running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1240233.1240238","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Strongly stable matchings in time\n            <i>O<\/i>\n            (\n            <i>nm<\/i>\n            ) and extension to the hospitals-residents problem"],"prefix":"10.1145","volume":"3","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Michail","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katarzyna E.","family":"Paluch","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroclaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"CaRMS (Canadian Resident Matching Service). 2007. How the matching algorithm works. http:\/\/www.carms.ca.  CaRMS (Canadian Resident Matching Service). 2007. How the matching algorithm works. http:\/\/www.carms.ca."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808776"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_4_1","unstructured":"Gusfield D. and Irving R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Boston MA.   Gusfield D. and Irving R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Boston MA."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00179-P"},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Annual European Symposium on Algorithms","author":"Irving R. W.","unstructured":"Irving , R. W. 1998. Matching medical students to pairs of hospitals: A new variation of a well-known theme . In Proceedings of the Annual European Symposium on Algorithms . Lecture Notes in Computer Science , vol. 1461 . Springer Verlag , Berlin . 381--392. Irving, R. W. 1998. Matching medical students to pairs of hospitals: A new variation of a well-known theme. In Proceedings of the Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1461. Springer Verlag, Berlin. 381--392."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2607","author":"Irving R. W.","unstructured":"Irving , R. W. , Manlove , D. F. , and Scott , S . 2003. Strong stability in the hospitals\/residents problem . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science , vol. 2607 . Springer Verlag, Berlin. 439--450. Irving, R. W., Manlove, D. F., and Scott, S. 2003. Strong stability in the hospitals\/residents problem. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607. Springer Verlag, Berlin. 439--450."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"1644","author":"Iwama K.","unstructured":"Iwama , K. , Manlove , D. , Miyazaki , S. , and Morita , Y . 1999. Stable marriage with incomplete lists and ties . In Proceedings of the International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science , vol. 1644 . Springer Verlag, Berlin. 443--452. Iwama, K., Manlove, D., Miyazaki, S., and Morita, Y. 1999. Stable marriage with incomplete lists and ties. In Proceedings of the International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1644. Springer Verlag, Berlin. 443--452."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Annual Symposium of Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2996","author":"Kavitha T.","unstructured":"Kavitha , T. , Mehlhorn , K. , Michail , D. , and Paluch , K. E . 2004. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem . In Proceedings of the Annual Symposium of Theoretical Aspects of Computer Science. Lecture Notes in Computer Science , vol. 2996 . Springer Verlag, Berlin. 222--232. Kavitha, T., Mehlhorn, K., Michail, D., and Paluch, K. E. 2004. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. In Proceedings of the Annual Symposium of Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996. Springer Verlag, Berlin. 222--232."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1086\/261272"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240238","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240238"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240238","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}