Optimal strategies for a model of combinatorial two-sided search
H. Aydinian, Ferdinando Cicalese, Christian Deppe, Vladimir S Lebedev · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2013
We introduce a new combinatorial search problem in networks.This search model can be viewed as an adaptive group testing in a graph, where a searching object, or target, occupies one of the vertices.However, unlike standard group testing problems, the target in our model can move to an adjacent vertex once after each test.The problem is to find the location of the target, with a certain accuracy, using minimum number of binary tests applied on the subsets of vertices of the underlying graph.In this paper we consider cycles and paths as underlying graphs.We give optimal search strategies for isolation of the target within a subset of vertices of a given size.We also considered a restricted case of the problem, when the number of moves of the target is limited.Finally we present a coding analogue of the problem.