{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:57Z","timestamp":1759639017163,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"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":[],"published-print":{"date-parts":[[2021,7,18]]},"DOI":"10.1145\/3465456.3467618","type":"proceedings-article","created":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T10:28:45Z","timestamp":1626604125000},"page":"319-339","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Stable Matchings with Restricted Preferences: Structure and Complexity"],"prefix":"10.1145","author":[{"given":"Christine T.","family":"Cheng","sequence":"first","affiliation":[{"name":"University of Wisconsin, Milwaukee, Milwaukee, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Will","family":"Rosenbaum","sequence":"additional","affiliation":[{"name":"Amherst College, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08)","author":"Bhatnagar Nayantara","year":"2008","unstructured":"Nayantara Bhatnagar , Sam Greenberg , and Dana Randall . 2008 . Sampling Stable Marriages: Why Spouse-swapping Won't Work . In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08) . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1223--1232. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347215 event-place: San Francisco, California. Nayantara Bhatnagar, Sam Greenberg, and Dana Randall. 2008. Sampling Stable Marriages: Why Spouse-swapping Won't Work. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1223--1232. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347215 event-place: San Francisco, California."},{"key":"e_1_3_2_1_2_1","series-title":"SIAM J. Comput","volume-title":"A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth","author":"Bodlaender Hans L.","year":"1996","unstructured":"Hans L. Bodlaender . 1996. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth . SIAM J. Comput ., Vol. 25 , 6 ( Dec. 1996 ), 1305--1317. https:\/\/doi.org\/10.1137\/S0097539793251219 Publisher : Society for Industrial and Applied Mathematics . Hans L. Bodlaender. 1996. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput., Vol. 25, 6 (Dec. 1996), 1305--1317. https:\/\/doi.org\/10.1137\/S0097539793251219 Publisher: Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2006.09.004"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.009"},{"key":"e_1_3_2_1_5_1","volume-title":"Leslie Ann Goldberg, and Russell Martin","author":"Chebolu Prasad","year":"2012","unstructured":"Prasad Chebolu , Leslie Ann Goldberg, and Russell Martin . 2012 . The complexity of approximately counting stable matchings. Theoretical Computer Science , Vol. 437 (June 2012), 35--68. https:\/\/doi.org\/10.1016\/j.tcs.2012.02.029 Prasad Chebolu, Leslie Ann Goldberg, and Russell Martin. 2012. The complexity of approximately counting stable matchings. Theoretical Computer Science, Vol. 437 (June 2012), 35--68. https:\/\/doi.org\/10.1016\/j.tcs.2012.02.029"},{"volume-title":"LATIN 2008: Theoretical Informatics (Lecture Notes in Computer Science )","author":"Cheng Christine T.","key":"e_1_3_2_1_6_1","unstructured":"Christine T. Cheng . 2008. The Generalized Median Stable Matchings: Finding Them Is Not That Easy . In LATIN 2008: Theoretical Informatics (Lecture Notes in Computer Science ) , Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, and Luerbio Faria (Eds.). Springer , Berlin, Heidelberg , 568--579. https:\/\/doi.org\/10.1007\/978--3--540--78773-0_49 Christine T. Cheng. 2008. The Generalized Median Stable Matchings: Finding Them Is Not That Easy. In LATIN 2008: Theoretical Informatics (Lecture Notes in Computer Science ), Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, and Luerbio Faria (Eds.). Springer, Berlin, Heidelberg, 568--579. https:\/\/doi.org\/10.1007\/978--3--540--78773-0_49"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9307-2"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.11.016"},{"key":"e_1_3_2_1_9_1","volume-title":"Cheng and Will Rosenbaum","author":"Christine","year":"2020","unstructured":"Christine T. Cheng and Will Rosenbaum . 2020 . Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth . arxiv: cs.DS\/2008.08479 Christine T. Cheng and Will Rosenbaum. 2020. Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth. arxiv: cs.DS\/2008.08479"},{"key":"e_1_3_2_1_10_1","volume-title":"Cheng and Will Rosenbaum","author":"Christine","year":"2021","unstructured":"Christine T. Cheng and Will Rosenbaum . 2021 . Stable Matchings with Restricted Preferences : Structure and Complexity . arxiv: cs.DM\/2008.08480 Christine T. Cheng and Will Rosenbaum. 2021. Stable Matchings with Restricted Preferences: Structure and Complexity. arxiv: cs.DM\/2008.08480"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00606-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"volume-title":"Stable networks and product graphs","author":"Feder Tom\u00e1s","key":"e_1_3_2_1_13_1","unstructured":"Tom\u00e1s Feder . 1995. Stable networks and product graphs . Vol. 555 . American Mathematical Soc . Tom\u00e1s Feder. 1995. Stable networks and product graphs. Vol. 555. American Mathematical Soc."},{"key":"e_1_3_2_1_14_1","volume-title":"Neighborly and Cyclic Polytopes. In Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, Victor Klee (Ed.)","volume":"7","author":"Gale David","year":"1963","unstructured":"David Gale . 1963 . Neighborly and Cyclic Polytopes. In Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, Victor Klee (Ed.) , Vol. 7 . American Mathematical Society. David Gale. 1963. Neighborly and Cyclic Polytopes. In Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, Victor Klee (Ed.), Vol. 7. American Mathematical Society."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.10.013"},{"key":"e_1_3_2_1_18_1","unstructured":"Sushmita Gupta Saket Saurabh and Meirav Zehavi. 2017. On Treewidth and Stable Marriage. _eprint: 1707.05404.  Sushmita Gupta Saket Saurabh and Meirav Zehavi. 2017. On Treewidth and Stable Marriage. _eprint: 1707.05404."},{"key":"e_1_3_2_1_19_1","series-title":"SIAM J. Comput","volume-title":"Three Fast Algorithms for Four Problems in Stable Marriage","author":"Gusfield Dan","year":"1987","unstructured":"Dan Gusfield . 1987. Three Fast Algorithms for Four Problems in Stable Marriage . SIAM J. Comput ., Vol. 16 , 1 ( Feb. 1987 ), 111--128. https:\/\/doi.org\/10.1137\/0216010 Publisher : Society for Industrial and Applied Mathematics . Dan Gusfield. 1987. Three Fast Algorithms for Four Problems in Stable Marriage. SIAM J. Comput., Vol. 16, 1 (Feb. 1987), 111--128. https:\/\/doi.org\/10.1137\/0216010 Publisher: Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_20_1","volume-title":"Irving","author":"Gusfield Dan","year":"1989","unstructured":"Dan Gusfield and Robert W . Irving . 1989 . The Stable marriage problem: structure and algorithms .MIT Press . Dan Gusfield and Robert W. Irving. 1989. The Stable marriage problem: structure and algorithms .MIT Press."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28871"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167200"},{"key":"e_1_3_2_1_24_1","unstructured":"Donald E. Knuth. 1976. Marriage stables et leurs relations avec d'autres probl\u00e8mes combinatoires. Les Presses de l'Universit\u00e9 de Montr\u00e9al.  Donald E. Knuth. 1976. Marriage stables et leurs relations avec d'autres probl\u00e8mes combinatoires. Les Presses de l'Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00564-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746598"},{"key":"e_1_3_2_1_27_1","series-title":"Series on Theoretical Computer Science","volume-title":"Algorithmics of Matching Under Preferences","author":"Manlove David F.","unstructured":"David F. Manlove . 2013. Algorithmics of Matching Under Preferences . Series on Theoretical Computer Science , Vol. 2 . World Scientific . https:\/\/doi.org\/10.1142\/8591 David F. Manlove. 2013. Algorithmics of Matching Under Preferences. Series on Theoretical Computer Science, Vol. 2. World Scientific. https:\/\/doi.org\/10.1142\/8591"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00206-7"},{"key":"e_1_3_2_1_29_1","first-page":"3","article-title":"Sex-Equal Stable Matchings","volume":"68","author":"McDermid Eric","year":"2014","unstructured":"Eric McDermid and Robert W. Irving . 2014 . Sex-Equal Stable Matchings : Complexity and Exact Algorithms. Algorithmica , Vol. 68 , 3 (March 2014), 545--570. https:\/\/doi.org\/10.1007\/s00453-012--9672-0 Eric McDermid and Robert W. Irving. 2014. Sex-Equal Stable Matchings: Complexity and Exact Algorithms. Algorithmica, Vol. 68, 3 (March 2014), 545--570. https:\/\/doi.org\/10.1007\/s00453-012--9672-0","journal-title":"Complexity and Exact Algorithms. Algorithmica"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219004"},{"key":"e_1_3_2_1_31_1","first-page":"425","article-title":"On the Allocation of Residents to Rural Hospitals","volume":"54","author":"Roth Alvin E.","year":"1986","unstructured":"Alvin E. Roth . 1986 . On the Allocation of Residents to Rural Hospitals : A General Property of Two-Sided Matching Markets. Econometrica , Vol. 54 , 2 (1986), 425 -- 427 . https:\/\/doi.org\/10.2307\/1913160 Publisher: [Wiley, Econometric Society]. Alvin E. Roth. 1986. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets. Econometrica, Vol. 54, 2 (1986), 425--427. https:\/\/doi.org\/10.2307\/1913160 Publisher: [Wiley, Econometric Society].","journal-title":"A General Property of Two-Sided Matching Markets. Econometrica"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.874"}],"event":{"name":"EC '21: The 22nd ACM Conference on Economics and Computation","sponsor":["SIGecom Special Interest Group on Economics and Computation"],"location":"Budapest Hungary","acronym":"EC '21"},"container-title":["Proceedings of the 22nd ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465456.3467618","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465456.3467618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:28Z","timestamp":1750191448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465456.3467618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":32,"alternative-id":["10.1145\/3465456.3467618","10.1145\/3465456"],"URL":"https:\/\/doi.org\/10.1145\/3465456.3467618","relation":{},"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"2021-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}