{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:08Z","timestamp":1750220108486,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T00:00:00Z","timestamp":1638403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1217314, CCF-1536026, and IIS-1619463"],"award-info":[{"award-number":["CCF-1217314, CCF-1536026, and IIS-1619463"]}]},{"name":"HKUST\/RGC","award":["FSGRF14EG28"],"award-info":[{"award-number":["FSGRF14EG28"]}]},{"name":"RGC CERG","award":["16208415 and 16213318"],"award-info":[{"award-number":["16208415 and 16213318"]}]},{"name":"NSERC and the Canada Research Chairs Programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            We present a simple\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            <jats:italic>)<\/jats:italic>\n            -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et\u00a0al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.\n          <\/jats:p>","DOI":"10.1145\/3477910","type":"journal-article","created":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T15:10:11Z","timestamp":1638457811000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Simple Algorithm\u00a0for Optimal Search Trees with Two-way Comparisons"],"prefix":"10.1145","volume":"18","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of California at Riverside, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mordecai","family":"Golin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[{"name":"Cherton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of California at Riverside, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,2]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00203-1"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211009"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1_28"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/320385.320407"},{"key":"e_1_3_3_6_2","first-page":"71","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201915) (Lecture Notes in Computer Science)","volume":"9472","author":"Chrobak M.","year":"2015","unstructured":"M. Chrobak, M. Golin, J. I. Munro, and N. E. Young. 2015. Optimal search trees with two-way comparisons. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201915) (Lecture Notes in Computer Science), Khaled Elbassioni and Kazuhisa Makino (Eds.), Vol. 9472. Springer, Berlin, 71\u201382. See Reference [9] for erratum. https:\/\/doi.org\/10.1007\/978-3-662-48971-0_7"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104707"},{"key":"e_1_3_3_8_2","unstructured":"M. Chrobak M. Golin J. I. Munro and N. E. Young. 2021. A simple algorithm for optimal search trees with two-way comparisons. Retrieved from https:\/\/arxiv2103.01084."},{"key":"e_1_3_3_9_2","unstructured":"M. Chrobak M. J. Golin J. I. Munro and N. E. Young. 2021. On Huang and Wong\u2019s algorithm for generalized binary split trees. Retrieved from https:\/\/arxiv1901.03783. To appear in Acta Informatica ."},{"key":"e_1_3_3_10_2","unstructured":"M. Chrobak M. J. Golin J. I. Munro and N. E. Young. 2021. Optimal search trees with two-way comparisons. Retrieved from https:\/\/arxiv1505.00357. Includes erratum for and pointers to journal versions of other results from Reference [5]."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1177299"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90031-3"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00101-X"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3465629"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/1051910"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/280635"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00320-9"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178732"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","unstructured":"D. Spuler. 1994. Optimal search trees using two-way key comparisons . Ph.D. Dissertation. James Cook University.","DOI":"10.1007\/BF01178732"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477910","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477910","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:37Z","timestamp":1750183837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,2]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3477910"],"URL":"https:\/\/doi.org\/10.1145\/3477910","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,12,2]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}