{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:49:33Z","timestamp":1743101373366,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_38","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"459-471","source":"Crossref","is-referenced-by-count":2,"title":["An Approximation Algorithm for Binary Searching in Trees"],"prefix":"10.1007","author":[{"given":"Eduardo","family":"Laber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","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.\u00a0321, 41\u201357 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR2","doi-asserted-by":"publisher","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 Transactions on Information Theory\u00a041, 287\u2013291 (1995)","journal-title":"IEEE Transactions on Information Theory"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM Journal on Computing\u00a028 (1999)","DOI":"10.1137\/S009753979731858X"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Onak, K., Parys, P.: Generalization of binary search: Searching in trees and forest-like partial orders. In: FOCS, pp. 379\u2013388 (2006)","DOI":"10.1109\/FOCS.2006.32"},{"key":"38_CR5","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an Optimal Tree Searching Strategy in Linear Time. In: SODA (2008)"},{"key":"38_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/11841036_28","volume-title":"Algorithms \u2013 ESA 2006","author":"K. Dou\u00efeb","year":"2006","unstructured":"Dou\u00efeb, K., Langerman, S.: Near-entropy hotlink assignments. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 292\u2013303. Springer, Heidelberg (2006)"},{"key":"38_CR7","doi-asserted-by":"publisher","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. Algorithms\u00a058, 81\u2013103 (2006)","journal-title":"J. Algorithms"},{"key":"38_CR8","doi-asserted-by":"publisher","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. Inform. Theory\u00a07, 27\u201339 (1961)","journal-title":"IRE Trans. Inform. Theory"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Golin, M., Kenyon, C., Young, N.: Huffman coding with unequal letter costs. In: STOC (2002)","DOI":"10.1145\/509907.510020"},{"key":"38_CR10","volume-title":"The art of computer programming, volume 3: sorting and searching","author":"D. Knuth","year":"1998","unstructured":"Knuth, D.: The art of computer programming, volume 3: sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City (1998)"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(93)90212-R","volume":"45","author":"R. de Prisco","year":"1993","unstructured":"de Prisco, R., de Santis, A.: On binary search trees. Inf. Process. Lett.\u00a045, 249\u2013253 (1993)","journal-title":"Inf. Process. Lett."},{"key":"38_CR12","doi-asserted-by":"publisher","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.\u00a017, 1203\u20131214 (1988)","journal-title":"SIAM J. Comput."},{"key":"38_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-48481-7_21","volume-title":"Algorithms - ESA\u201999","author":"E. Laber","year":"1999","unstructured":"Laber, E., Milidi\u00fa, R., Pessoa, A.: Strategies for searching with different access costs. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 236\u2013247. Springer, Heidelberg (1999)"},{"key":"38_CR14","unstructured":"Laber, E., Milidi\u00fa, R., Pessoa, A.: On binary searching with non-uniform costs. In: SODA, pp. 855\u2013864 (2001)"},{"key":"38_CR15","doi-asserted-by":"publisher","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\u00a027, 145\u2013169 (2000)","journal-title":"Algorithmica"},{"key":"38_CR16","doi-asserted-by":"publisher","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., Oliveira, J., Cunto, W., Ziviani, N.: Optimal binary search trees with costs depending on the access paths. Theor. Comput. Sci.\u00a0290, 1799\u20131814 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Algorithms and Data Structures","author":"R. Kosaraju","year":"1999","unstructured":"Kosaraju, R., Przytycka, T., Borgstrom, R.: On an optimal split tree problem. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663. Springer, Heidelberg (1999)"},{"key":"38_CR18","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0144, 209\u2013212 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision trees for entity identification: approximation algorithms and hardness results. In: PODS, pp. 53\u201362 (2007)","DOI":"10.1145\/1265530.1265538"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:28:24Z","timestamp":1714620504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}