{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:45Z","timestamp":1750220625291,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1464276,CCF-1909171,CCF-1617851"],"award-info":[{"award-number":["CCF-1464276,CCF-1909171,CCF-1617851"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            Given a weighted planar bipartite graph\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>A<\/jats:italic>\n            \u222a\n            <jats:italic>B<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) where each edge has an integer edge cost, we give an \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            log\n            <jats:italic>nC<\/jats:italic>\n            ) time algorithm to compute minimum-cost perfect matching; here\n            <jats:italic>C<\/jats:italic>\n            is the maximum edge cost in the graph. The previous best-known planarity exploiting algorithm has a running time of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) and is achieved by using planar separators (Lipton and Tarjan \u201980).\n          <\/jats:p>\n          <jats:p>\n            Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan \u201989). For each scale, our algorithm first executes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/3<\/jats:sup>\n            ) iterations of Gabow and Tarjan\u2019s algorithm in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) time leaving only\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) vertices unmatched. Next, it constructs a compressed residual graph\n            <jats:italic>H<\/jats:italic>\n            with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) vertices and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) edges. This is achieved by using an\n            <jats:italic>r<\/jats:italic>\n            -division of the planar graph\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>r<\/jats:italic>\n            =\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            . For each partition of the\n            <jats:italic>r<\/jats:italic>\n            -division, there is an edge between two vertices of\n            <jats:italic>H<\/jats:italic>\n            if and only if they are connected by a directed path inside the partition. Using existing efficient shortest-path data structures, the remaining\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) vertices are matched by iteratively computing a minimum-cost augmenting path, each taking \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) time. Augmentation changes the residual graph, so the algorithm updates the compressed representation for each partition affected by the change in \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) time. We bound the total number of affected partitions over all the augmenting paths by\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ). Therefore, the total time taken by the algorithm is \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3365006","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs"],"prefix":"10.1145","volume":"16","author":[{"given":"Mudabir Kabir","family":"Asathulla","sequence":"first","affiliation":[{"name":"Virginia Tech, Blacksburg, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathaniel","family":"Lahn","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharath","family":"Raghvendra","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","year":"2001","author":"Biedl Therese","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1042929"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.48"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972924.4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-024-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"H. N. Gabow and R. E. Tarjan. 1989. Faster scaling algorithms for network problems. SIAM J. Comput. 18 (Oct. 1989) 1013--1036. Issue 5. DOI:https:\/\/doi.org\/10.1137\/0218069  H. N. Gabow and R. E. Tarjan. 1989. Faster scaling algorithms for network problems. SIAM J. Comput. 18 (Oct. 1989) 1013--1036. Issue 5. DOI:https:\/\/doi.org\/10.1137\/0218069","DOI":"10.1137\/0218069"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Improved bounds for shortest paths in dense distance graphs. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918), Vol. 107. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl","volume":"61","author":"Gawrychowski Pawel","year":"2018","journal-title":"Germany"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_10_1","first-page":"26","article-title":"Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications","volume":"13","author":"Kaplan Haim","year":"2017","journal-title":"ACM Trans. Alg."},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","year":"2005","author":"Klein Philip","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030404"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201910)","year":"2010","author":"Mozes Shay","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1187-5"},{"volume-title":"Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS\u201912)","year":"2012","author":"Ramshaw L.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.028"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2480283"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365006","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:29Z","timestamp":1750197689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3365006"],"URL":"https:\/\/doi.org\/10.1145\/3365006","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}