Optimal Search in Trees

DOI10.1137/S009753979731858XzbMath0939.68022MaRDI QIDQ4268858

Yosi Ben-Asher, Ilan Newman, Eitan Farchi

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

posetsbinary searchoptimal searchsearch in graphssearch in trees

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (20)

Tree edge decomposition with an application to minimum ultrametric tree approximation ⋮ On the tree search problem with non-uniform costs ⋮ Searching for quicksand ideals in partially ordered sets ⋮ On searching a table consistent with division poset ⋮ Searching in random partially ordered sets ⋮ Theoretical analysis of git bisect ⋮ Edge and pair queries-random graphs and complexity ⋮ An approximation algorithm for binary searching in trees ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Binary search in graphs revisited ⋮ Searching a Tree with Permanently Noisy Advice ⋮ Edge ranking and searching in partial orders ⋮ The binary identification problem for weighted trees ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ On the Tree Search Problem with Non-uniform Costs ⋮ Binary Search in Graphs Revisited ⋮ Competitive Online Search Trees on Trees ⋮ An efficient noisy binary search in graphs via Median approximation

This page was built for publication: Optimal Search in Trees