1 paper · 2 filters
Lukas Michel, Alex Scott
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $Ω(Δ^2 \…