Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418844 | Discrete Applied Mathematics | 2015 | 9 Pages |
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
Younjin Kim, Mohit Kumbhat, Zoltán Lóránt Nagy, Balázs Patkós, Alexey Pokrovskiy, Máté Vizer,