{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:25:29Z","timestamp":1772043929211,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T00:00:00Z","timestamp":1242777600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s00453-009-9325-0","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T13:22:08Z","timestamp":1242739328000},"page":"601-620","source":"Crossref","is-referenced-by-count":9,"title":["An Approximation Algorithm for Binary Searching in\u00a0Trees"],"prefix":"10.1007","volume":"59","author":[{"given":"Eduardo","family":"Laber","sequence":"first","affiliation":[]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,20]]},"reference":[{"issue":"4","key":"9325_CR1","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1006\/jcss.2001.1779","volume":"63","author":"M. Adler","year":"2001","unstructured":"Adler, M., Maggs, B.: Protocols for asymmetric communication channels. J.\u00a0Comput. Syst. Sci. 63(4), 573\u2013596 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9325_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/1109557.1109586","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006","author":"M. Adler","year":"2006","unstructured":"Adler, M., Demaine, E., Harvey, N., Patrascu, M.: Lower bounds for asymmetric communication channels and distributed source coding. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, 22\u201326 January 2006. pp. 251\u2013260. ACM Press, New York (2006)"},{"issue":"2","key":"9325_CR3","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.jalgor.2005.06.001","volume":"58","author":"A. Barkan","year":"2006","unstructured":"Barkan, A., Kaplan, H.: Partial alphabetic trees. J.\u00a0Algorithms 58(2), 81\u2013103 (2006)","journal-title":"J.\u00a0Algorithms"},{"issue":"6","key":"9325_CR4","doi-asserted-by":"crossref","first-page":"2090","DOI":"10.1137\/S009753979731858X","volume":"28","author":"Y. Ben-Asher","year":"1999","unstructured":"Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J.\u00a0Comput. 28(6), 2090\u20132102 (1999)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1","key":"9325_CR5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2003.06.001","volume":"321","author":"R. Carmo","year":"2004","unstructured":"Carmo, R., Donadelli, J., Kohayakawa, Y., Laber, E.: Searching in random partially ordered sets. Theor. Comput. Sci. 321(1), 41\u201357 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9325_CR6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/1265530.1265538","volume-title":"Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)","author":"V. Chakaravarthy","year":"2007","unstructured":"Chakaravarthy, V., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision trees for entity identification: Approximation algorithms and hardness results. In: Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Beijing, China, 11\u201313 June 2007, pp. 53\u201362. ACM, New York (2007)"},{"issue":"5","key":"9325_CR7","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(93)90212-R","volume":"45","author":"R. Prisco de","year":"1993","unstructured":"de Prisco, R., de Santis, A.: On binary search trees. Inf. Process. Lett. 45(5), 249\u2013253 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9325_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/11841036_28","volume-title":"Algorithms\u2014ESA 2006, Proceedings of 14th Annual European Symposium","author":"K. Dou\u00efeb","year":"2006","unstructured":"Dou\u00efeb, K., Langerman, S.: Near-entropy hotlink assignments. In: Azar, Y., Erlebach, T. (eds.) Algorithms\u2014ESA 2006, Proceedings of 14th Annual European Symposium, Zurich, Switzerland, 11\u201313 September 2006. Lecture Notes in Computer Science, vol. 4168, pp. 292\u2013303. Springer, Berlin (2006)"},{"key":"9325_CR9","volume-title":"Information Theory and Reliable Communication","author":"R. Gallager","year":"1968","unstructured":"Gallager, R.: Information Theory and Reliable Communication. Wiley, New York (1968)"},{"key":"9325_CR10","unstructured":"Ghazizadeh, S., Ghodsi, M., Saberi, A.: A new protocol for asymmetric communication channels: Reaching the lower bounds. Scientia Iranica 8(4) (2001)"},{"key":"9325_CR11","first-page":"785","volume-title":"Proceedings of 34th Annual ACM Symposium on Theory of Computing","author":"M. Golin","year":"2002","unstructured":"Golin, M., Kenyon, C., Young, N.: Huffman coding with unequal letter costs. In: Proceedings of 34th Annual ACM Symposium on Theory of Computing, Montr\u00e9al, Qu\u00e9bec, Canada, 19\u201321 May 2002, pp.\u00a0785\u2013791. ACM, New York (2002)"},{"issue":"1","key":"9325_CR12","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TIT.1961.1057615","volume":"7","author":"R. Karp","year":"1961","unstructured":"Karp, R.: Minimum-redundancy coding for the discrete noiseless channel. IRE Trans. Inf. Theory 7(1), 27\u201338 (1961)","journal-title":"IRE Trans. Inf. Theory"},{"issue":"6","key":"9325_CR13","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1137\/0217076","volume":"17","author":"W. Knight","year":"1988","unstructured":"Knight, W.: Search in an ordered array having variable probe cost. SIAM J. Comput. 17(6), 1203\u20131214 (1988)","journal-title":"SIAM J. Comput."},{"key":"9325_CR14","volume-title":"The Art of Computer Programming, vol.\u00a03: Sorting and Searching","author":"D. Knuth","year":"1998","unstructured":"Knuth, D.: The Art of Computer Programming, vol.\u00a03: Sorting and Searching. Addison-Wesley\/Longman, Redwood City (1998)"},{"key":"9325_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Proceedings of 6th International Workshop on Algorithms and Data Structures, WADS \u201999","author":"R. Kosaraju","year":"1999","unstructured":"Kosaraju, R., Przytycka, T., Borgstrom, R.: On an optimal split tree problem. In: Dehne, F.K.H.A., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) Proceedings of 6th International Workshop on Algorithms and Data Structures, WADS \u201999, Vancouver, British Columbia, Canada, 11\u201314 August 1999. Lecture Notes in Computer Science, vol. 1663, pp. 157\u2013168. Springer, Berlin (1999)"},{"issue":"4","key":"9325_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0020-0190(01)00332-5","volume":"83","author":"E. Laber","year":"2002","unstructured":"Laber, E., Holanda, L.: Improved bounds for asymmetric communication protocols. Inf. Process. Lett. 83(4), 205\u2013209 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"9325_CR17","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.dam.2004.06.002","volume":"144","author":"E. Laber","year":"2004","unstructured":"Laber, E., Nogueira, L.: On the hardness of the minimum height decision tree problem. Discrete Appl. Math. 144(1\u20132), 209\u2013212 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9325_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-48481-7_21","volume-title":"Proceedings of 7th Annual European Symposium, Algorithms\u2014ESA \u201999","author":"E. Laber","year":"1999","unstructured":"Laber, E., Milidi\u00fa, R., Pessoa, A.: Strategies for searching with different access costs. In: Nesetril, J. (ed.) Proceedings of 7th Annual European Symposium, Algorithms\u2014ESA \u201999, Prague, Czech Republic, 16\u201318 July 1999. Lecture Notes in Computer Science, vol. 1643, pp. 236\u2013247. Springer, Berlin (1999)"},{"key":"9325_CR19","first-page":"855","volume-title":"Proceedings of the Twelfth Annual Symposium on Discrete Algorithms","author":"E. Laber","year":"2001","unstructured":"Laber, E., Milidi\u00fa, R., Pessoa, A.: On binary searching with non-uniform costs. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, Washington, DC, USA, 7\u20139 January 2001, pp. 855\u2013864. ACM\/SIAM, New York\/Philadelphia (2001)"},{"issue":"1","key":"9325_CR20","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1109\/18.370098","volume":"41","author":"M. Lipman","year":"1995","unstructured":"Lipman, M., Abrahams, J.: Minimum average cost testing for partially ordered components. IEEE Trans. Inf. Theory 41(1), 287\u2013291 (1995)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9325_CR21","first-page":"1096","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"S. Mozes","year":"2008","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: Teng, S.-H. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, 20\u201322 January 2008, pp. 1096\u20131105. SIAM, Philadelphia (2008)"},{"issue":"2","key":"9325_CR22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s004530010010","volume":"27","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R., Barbosa, E., Ziviani, N., Cunto, W.: Binary searching with nonuniform costs and its application to text retrieval. Algorithmica 27(2), 145\u2013169 (2000)","journal-title":"Algorithmica"},{"key":"9325_CR23","first-page":"379","volume-title":"Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science","author":"K. Onak","year":"2006","unstructured":"Onak, K., Parys, P.: Generalization of binary search: Searching in trees and forest-like partial orders. In: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, USA, 21\u201324 October, 2006. pp. 379\u2013388. IEEE Computer Society, Los Alamitos (2006)"},{"issue":"3","key":"9325_CR24","doi-asserted-by":"crossref","first-page":"1799","DOI":"10.1016\/S0304-3975(02)00084-1","volume":"290","author":"J. Szwarcfiter","year":"2003","unstructured":"Szwarcfiter, J., Navarro, G., Baeza-Yates, R., de S.\u00a0Oliveira, J., Cunto, W., Ziviani, N.: Optimal binary search trees with costs depending on the access paths. Theor. Comput. Sci. 290(3), 1799\u20131814 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9325_CR25","unstructured":"Watkinson, J., Adler, M., Fich, F.: New protocols for asymmetric communication channels. In: Comellas, F., F\u00e0brega, J., Fraigniaud, P. (eds.) Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u00a08), Vall de N\u00faria, Girona\u2013Barcelona, Catalonia, Spain, 27\u201329 June 2001. Proceedings in Informatics, vol. 8, pp. 337\u2013350. Carleton Scientific (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9325-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9325-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9325-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:04Z","timestamp":1559123104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9325-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,20]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9325"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9325-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,20]]}}}