Paper Info
Title
On the complexity of searching in trees: average-case minimization
Abstract
The well known binary search method can be described as the process of identifying some marked node from a line graph T by successively querying edges. An edge query e asks in which of the two subpaths induced by T \ e the marked node lies. This procedure can be naturally generalized to the case where T = (V,E) is a tree instead of a line. The problem of determining a tree search strategy minimizing the number of queries in the worst case is solvable in linear time [Onak etal. FOCS'06, Mozes et al. SODA'08]. Here we study the average-case problem, where the objective function is the weighted average number of queries to find a node An involved analysis shows that the problem is NP-complete even for the class of trees with bounded diameter, or bounded degree. We also show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O(Δ(T)(log |V | +log w (T))) queries in the worst case, where w(T) is the sum of the node weights and Δ(T) is the maximum degree of T. This structural property is then combined with a non-trivial exponential time algorithm to provide an FPTAS for the bounded degree case.
Year
DOI
Venue
2010
10.1007/978-3-642-14165-2_45
international colloquium on automata, languages and programming
Keywords
DocType
Volume
node weight,bounded degree,maximum degree,weighted average number,expected number,marked node,bounded diameter,worst case,average-case minimization,bounded degree case,average-case problem
Conference
abs/0904.3503
ISSN
ISBN
Citations 
0302-9743
3-642-14164-1
7
PageRank 
References 
Authors
0.47
26
4
Name
Order
Citations
PageRank
Tobias Jacobs1544.32
Ferdinando Cicalese245048.20
Eduardo Laber3435.55
Marco Molinaro416418.75