Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00453-009-9325-0 | Algorithmica |
Keywords | Field | DocType |
binary search · partially ordered sets · trees · approximation algorithms,binary search,software testing | Approximation algorithm,Combinatorics,Computer science,Interpolation search,Self-balancing binary search tree,Theoretical computer science,Fringe search,Jump search,Binary search algorithm,Time complexity,Ternary search tree | Journal |
Volume | Issue | ISSN |
59 | 4 | 0178-4617 |
Citations | PageRank | References |
8 | 0.50 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Sany Laber | 1 | 229 | 27.12 |
| Marco Molinaro | 2 | 164 | 18.75 |