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 et al. 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 -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| + logw(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.

On the Complexity of Searching in Trees: Average-Case Minimization

CICALESE, Ferdinando;
2010-01-01

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 et al. 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 -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| + logw(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.
2010
9783642141645
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/3011902
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact