Deterministic and probabilistic binary search in graphs

DOI10.1145/2897518.2897656zbMath1376.68064arXiv1503.00805OpenAlexW2395495808MaRDI QIDQ5361858

Ehsan Emamjomeh-Zadeh, Vikrant Singhal, David Kempe

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.00805

zbMATH Keywords

exponential-time hypothesisPSPACE-hardnessnoisy binary searchquasipolynomial-time algorithmssearching in metric spaces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Theoretical analysis of git bisect ⋮ Edge and pair queries-random graphs and complexity ⋮ Binary search in graphs revisited ⋮ Searching a Tree with Permanently Noisy Advice ⋮ The tree search game for two players ⋮ On the diameter of tree associahedra ⋮ The complexity of bicriteria tree-depth ⋮ Binary Search in Graphs Revisited ⋮ Sequential metric dimension for random graphs ⋮ Competitive Online Search Trees on Trees ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ The power of adaptivity in source identification with time queries on the path