{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T12:29:06Z","timestamp":1768739346722,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217314"],"award-info":[{"award-number":["CCF-1217314"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1536026"],"award-info":[{"award-number":["CCF-1536026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IS-1619463"],"award-info":[{"award-number":["IS-1619463"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["16208415"],"award-info":[{"award-number":["16208415"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["Research Grants Council, University Grants Committee"],"award-info":[{"award-number":["Research Grants Council, University Grants Committee"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Huang and Wong (Acta Inform 21(1):113\u2013123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong\u2019s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler\u2019s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.\n<\/jats:p>","DOI":"10.1007\/s00236-021-00411-z","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T13:41:43Z","timestamp":1644846103000},"page":"687-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On Huang and Wong\u2019s algorithm for generalized binary split trees"],"prefix":"10.1007","volume":"59","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1260-6574","authenticated-orcid":false,"given":"Mordecai","family":"Golin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"411_CR1","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/S0196-6774(02)00203-1","volume":"44","author":"R Anderson","year":"2002","unstructured":"Anderson, R., Kannan, S., Karloff, H., Ladner, R.E.: Thresholds and optimal binary comparison search trees. J. Algorithms 44, 338\u2013358 (2002)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"411_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1080\/00207169108804024","volume":"41","author":"G-H Chen","year":"1991","unstructured":"Chen, G.-H., Liu, L.-T.: Optimal multiway generalized split trees. Int. J. Comput. Math. 41(1\u20132), 39\u201347 (1991)","journal-title":"Int. J. Comput. Math."},{"key":"411_CR3","series-title":"ISAAC 2015, volume 9472 of Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-662-48971-0_7","volume-title":"Algorithms and Computation","author":"M Chrobak","year":"2015","unstructured":"Chrobak, M., Golin, M., Munro, J.I., Young, N.E.: Optimal search trees with 2-way comparisons. In: Elbassioni, K., Makino, K. (eds.) Algorithms and Computation. ISAAC 2015, volume 9472 of Lecture Notes in Computer Science, pp. 71\u201382. Springer, Berlin (2015) . (See [4] for erratum)"},{"key":"411_CR4","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Golin, M., Munro, J.I., Young, N.E.: Optimal search trees with two-way comparisons (2021). arXiv:1505.00357 (Includes erratum for [3])","DOI":"10.1145\/3477910"},{"key":"411_CR5","doi-asserted-by":"publisher","unstructured":"Chrobak, M., Golin, M., Munro, J.I., Young, N.E.: A simple algorithm for optimal search trees with two-way comparisons. ACM Trans. Algorithms 18(1), 11 (2022). https:\/\/doi.org\/10.1145\/3477910","DOI":"10.1145\/3477910"},{"key":"411_CR6","doi-asserted-by":"publisher","first-page":"104707","DOI":"10.1016\/j.ic.2021.104707","volume":"281","author":"M Chrobak","year":"2021","unstructured":"Chrobak, M., Golin, M., Munro, J.I., Young, N.E.: On the cost of unsuccessful searches in search trees with two-way comparisons. Inf. Comput. 281, 104707 (2021). https:\/\/doi.org\/10.1016\/j.ic.2021.104707","journal-title":"Inf. Comput."},{"key":"411_CR7","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/0196-6774(86)90031-3","volume":"7","author":"JH Hester","year":"1986","unstructured":"Hester, J.H., Hirschberg, D.S., Huang, S.H., Wong, C.K.: Faster construction of optimal binary split trees. J. Algorithms 7, 412\u2013424 (1986)","journal-title":"J. Algorithms"},{"issue":"1","key":"411_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF00289143","volume":"21","author":"S-HS Huang","year":"1984","unstructured":"Huang, S.-H.S., Wong, C.K.: Generalized binary split trees. Acta Inform. 21(1), 113\u2013123 (1984)","journal-title":"Acta Inform."},{"key":"411_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0196-6774(84)90041-5","volume":"5","author":"S-HS Huang","year":"1984","unstructured":"Huang, S.-H.S., Wong, C.K.: Optimal binary split trees. J. Algorithms 5, 69\u201379 (1984)","journal-title":"J. Algorithms"},{"key":"411_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"DE Knuth","year":"1971","unstructured":"Knuth, D.E.: Optimum binary search trees. Acta Inform. 1, 14\u201325 (1971)","journal-title":"Acta Inform."},{"key":"411_CR11","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edn. Addison-Wesley Publishing Company, Redwood City (1998)","edition":"2"},{"key":"411_CR12","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0196-6774(84)90017-8","volume":"5","author":"Y Perl","year":"1984","unstructured":"Perl, Y.: Optimum split trees. J. Algorithms 5, 367\u2013374 (1984)","journal-title":"J. Algorithms"},{"key":"411_CR13","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1145\/359642.359653","volume":"21","author":"BA Sheil","year":"1978","unstructured":"Sheil, B.A.: Median split trees: a fast lookup technique for frequently occurring keys. Commun. ACM 21, 947\u2013958 (1978)","journal-title":"Commun. ACM"},{"issue":"8","key":"411_CR14","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/BF01178732","volume":"31","author":"D Spuler","year":"1994","unstructured":"Spuler, D.: Optimal search trees using two-way key comparisons. Acta Inform. 31(8), 729\u2013740 (1994)","journal-title":"Acta Inform."},{"key":"411_CR15","doi-asserted-by":"crossref","unstructured":"Spuler, D.: Optimal search trees using two-way key comparisons. PhD thesis, James Cook University (1994)","DOI":"10.1007\/BF01178732"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00411-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00411-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00411-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T06:08:47Z","timestamp":1666332527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00411-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,14]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["411"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00411-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,14]]},"assertion":[{"value":"6 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}