caa a22 4500 445804939 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9325-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9325-0 An Approximation Algorithm for Binary Searching inTrees [Elektronische Daten] [Eduardo Laber, Marco Molinaro] We consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation. Springer Science+Business Media, LLC, 2009 Binary search nationallicence Partially ordered sets nationallicence Trees nationallicence Approximation algorithms nationallicence Laber Eduardo Informatics Department, PUC-Rio, Rua Marquês de São Vicente 225, RDC, 4º andar, CEP 22453-900, Rio de Janeiro, RJ, Brazil aut Molinaro Marco Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA aut Algorithmica Springer-Verlag 59/4(2011-04-01), 601-620 0178-4617 59:4<601 2011 59 453 https://doi.org/10.1007/s00453-009-9325-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9325-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Laber Eduardo Informatics Department, PUC-Rio, Rua Marquês de São Vicente 225, RDC, 4º andar, CEP 22453-900, Rio de Janeiro, RJ, Brazil aut NATIONALLICENCE 700 1- Molinaro Marco Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 601-620 0178-4617 59:4<601 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer