A Combinatorial Model of Two-Sided Search

Aydinian H, Cicalese F, Deppe C, Lebedev V (2018)
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 29(4): 481-504.

Zeitschriftenaufsatz | Veröffentlicht| Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor*in
Aydinian, Harout; Cicalese, Ferdinando; Deppe, ChristianUniBi; Lebedev, Vladimir
Abstract / Bemerkung
We study a new model of combinatorial group testing: the item to be found (a.k.a. the target) occupies an unknown node in a graph. At each time instant, we can test (or query) a subset of the nodes and learn whether the target occupies any of such nodes. Immediately after the result of the test is available, the target can move to any node adjacent to its present location. The search finishes when we are able to locate the object with some predefined accuracy s (a parameter fixed beforehand), i.e., to indicate a set of s nodes that includes the location of the object. In this paper we study two types of problems related to the above model: (i) what is the minimum value of the accuracy parameter for which a search strategy in the above sense exists; (ii) given the accuracy, what is the minimum number of tests that allow to locate the target. We study these questions on paths, cycles, and trees as underlying graphs and provide tight answers for the above questions. We also consider a restricted variant of the problem, where the number of moves of the target is bounded.
Stichworte
Adaptive search; two-sided search; search in graphs
Erscheinungsjahr
2018
Zeitschriftentitel
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Band
29
Ausgabe
4
Seite(n)
481-504
ISSN
0129-0541
eISSN
1793-6373
Page URI
https://pub.uni-bielefeld.de/record/2930283

Zitieren

Aydinian H, Cicalese F, Deppe C, Lebedev V. A Combinatorial Model of Two-Sided Search. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. 2018;29(4):481-504.
Aydinian, H., Cicalese, F., Deppe, C., & Lebedev, V. (2018). A Combinatorial Model of Two-Sided Search. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(4), 481-504. doi:10.1142/S0129054118410022
Aydinian, H., Cicalese, F., Deppe, C., and Lebedev, V. (2018). A Combinatorial Model of Two-Sided Search. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 29, 481-504.
Aydinian, H., et al., 2018. A Combinatorial Model of Two-Sided Search. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(4), p 481-504.
H. Aydinian, et al., “A Combinatorial Model of Two-Sided Search”, INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, vol. 29, 2018, pp. 481-504.
Aydinian, H., Cicalese, F., Deppe, C., Lebedev, V.: A Combinatorial Model of Two-Sided Search. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. 29, 481-504 (2018).
Aydinian, Harout, Cicalese, Ferdinando, Deppe, Christian, and Lebedev, Vladimir. “A Combinatorial Model of Two-Sided Search”. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 29.4 (2018): 481-504.