Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-044 | 20th March 1997 00:00

Optimal Search in Trees Revision of: TR96-044

RSS-Feed




Revision #1
Authors: Yosi Ben-Asher, Eitan Farchi, Ilan Newman
Accepted on: 20th March 1997 00:00
Downloads: 3061
Keywords: 


Abstract:


It is well known that the optimal solution for
searching in a finite total order set is binary search.
In binary search we divide the set into two ``halves'' by querying the middle
element and continue the search on the suitable half.
What is the equivalent of binary search when
the set $P$ is partially ordered?
A query in this case is to a point $x\in P$, with
two possible answers: 'yes', indicates that the required element
is ``below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
polynomial in the size of the tree, and requires at most $O(n^4\log^3 n)$ steps.

Optimal solutions of such search problems are often
needed in program testing and debugging,
where a given program is represented as a tree
and a bug should be found using a minimal set of queries.
This type of search is also applicable in searching
classified large tree-like data bases (e.g. the Internet).


Paper:

TR96-044 | 6th August 1996 00:00

Optimal Search in Trees





TR96-044
Authors: Yosi Ben-Asher, Ilan Newman
Publication: 26th August 1996 12:05
Downloads: 2257
Keywords: 


Abstract:

It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two ``halves'', by querying the middle
element, and continue the search on the suitable half.
What is the equivalent of binary search, when
the set $P$ is partially ordered?
A query in this case is to a point $x\in P$, with
two possible answers: 'yes', indicates that the required element
is ``below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
polynomial in the size of
the tree, and requires at most $O(n^2\log^2 n)$ steps.

Optimal solutions of such search problems are often
needed in program testing and debugging,
where a given program is represented as a tree
and a bug should be found using a minimal set of queries.



ISSN 1433-8092 | Imprint