An Approximation Algorithm for Binary Searching in Trees

An Approximation Algorithm for Binary Searching in Trees

0.00 Avg rating0 Votes
Article ID: iaor20112415
Volume: 59
Issue: 4
Start Page Number: 601
End Page Number: 620
Publication Date: Apr 2011
Journal: Algorithmica
Authors: ,
Keywords: search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.