An Efficient Noisy Binary Search in Graphs via Median Approximation

Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański

Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a…