{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:03:04Z","timestamp":1743058984639,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":10,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819723393"},{"type":"electronic","value":"9789819723409"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-2340-9_9","type":"book-chapter","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:01:51Z","timestamp":1714690911000},"page":"99-110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Tight Threshold Bound for\u00a0Search Trees with\u00a02-Way Comparisons"],"prefix":"10.1007","author":[{"given":"Sunny","family":"Atalig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"9_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"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Atalig, S., Chrobak, M., Mousavian, E., Sgall, J., Vesely, P.: Structural properties of search trees with 2-way comparisons. CoRR, abs\/2311.02224 (2023)","DOI":"10.1007\/978-981-97-2340-9_9"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644032","volume":"6","author":"W Bein","year":"2009","unstructured":"Bein, W., Golin, M.J., Larmore, L.L., Zhang, Y.: The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity. ACM Trans. Algorithms 6(1), 1\u201317 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3477910","volume":"18","author":"M Chrobak","year":"2021","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), 1\u201311 (2021)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"9_CR5","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s00236-021-00411-z","volume":"59","author":"M Chrobak","year":"2022","unstructured":"Chrobak, M., Golin, M., Munro, J.I., Young, N.E.: On Huang and Wong\u2019s algorithm for generalized binary split trees. Acta Informatica 59(6), 687\u2013708 (2022)","journal-title":"Acta Informatica"},{"key":"9_CR6","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 Informatica 1, 14\u201325 (1971)","journal-title":"Acta Informatica"},{"key":"9_CR7","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"},{"issue":"8","key":"9_CR8","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 Informatica 31(8), 729\u2013740 (1994)","journal-title":"Acta Informatica"},{"key":"9_CR9","unstructured":"Spuler, D.A.: Optimal search trees using two-way key comparisons. PhD thesis, James Cook University (994)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Yao, F.F.: Efficient dynamic programming using quadrangle inequalities. In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds.) Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 28\u201330 April 1980, Los Angeles, California, USA, pp. 429\u2013435. ACM (1980)","DOI":"10.1145\/800141.804691"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-2340-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T23:17:27Z","timestamp":1731885447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-2340-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819723393","9789819723409"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-2340-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tamc2024.comp.polyu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}