Article ID Journal Published Year Pages File Type
418844 Discrete Applied Mathematics 2015 9 Pages PDF
Abstract

Given a graph GG and a positive integer RR we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form “does an unknown vertex v∈V(G)v∈V(G) belong to the ball of radius rr around uu?” with u∈V(G)u∈V(G) and r≤Rr≤R that is needed to determine vv. We consider both the adaptive case when the jjth query might depend on the answers to the previous queries and the non-adaptive case when all queries must be made at once. We obtain bounds on the minimum number of queries for hypercubes, the Erdős–Rényi random graphs and graphs of bounded maximum degree.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , ,