Geodesic
Graph Searching Games with a Radius of Capture
Contributions to game theory and management, Tome 4 (2011), pp. 8-18 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of guaranteed search on graphs, the so-called $\varepsilon$-search problem, is considered. The properties of the Golovach function which is the $\varepsilon$-search number as the function of the radius of capture $\varepsilon$ are studied. In the present work, we show that the jumps of the Golovach function for trees may have an arbitrarily large height. We describe some classes of trees with the non-degenerate Golovach function, and construct the minimal tree with a non-unit jump.
Keywords: guaranteed search, team of pursuers, evader, $\varepsilon$-capture, search numbers, Golovach function, unit jumps. 
@article{CGTM_2011_4_a1,
     author = {Tatiana V. Abramovskaya and Nikolai N. Petrov},
     title = {Graph {Searching} {Games} with a {Radius} of {Capture}},
     journal = {Contributions to game theory and management},
     pages = {8--18},
     year = {2011},
     volume = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2011_4_a1/}
}
TY  - JOUR
AU  - Tatiana V. Abramovskaya
AU  - Nikolai N. Petrov
TI  - Graph Searching Games with a Radius of Capture
JO  - Contributions to game theory and management
PY  - 2011
SP  - 8
EP  - 18
VL  - 4
UR  - http://geodesic.mathdoc.fr/item/CGTM_2011_4_a1/
LA  - en
ID  - CGTM_2011_4_a1
ER  - 
%0 Journal Article
%A Tatiana V. Abramovskaya
%A Nikolai N. Petrov
%T Graph Searching Games with a Radius of Capture
%J Contributions to game theory and management
%D 2011
%P 8-18
%V 4
%U http://geodesic.mathdoc.fr/item/CGTM_2011_4_a1/
%G en
%F CGTM_2011_4_a1
Tatiana V. Abramovskaya; Nikolai N. Petrov. Graph Searching Games with a Radius of Capture. Contributions to game theory and management, Tome 4 (2011), pp. 8-18. http://geodesic.mathdoc.fr/item/CGTM_2011_4_a1/

[1] Abramovskaya T. V., “Nontrivial discontinuities of the Golovach functions for trees”, Vestnik St. Petersburg Univ. Math., 43:3 (2010), 123–130 | DOI | MR | Zbl

[2] Abramovskaya T. V., Petrov N. N., “On some problems of guaranteed search on graphs”, Vestnik St. Petersburg Univ. Math., 43:2 (2010), 68–73 | DOI | MR | Zbl

[3] Breisch R., “An intuitive approach to speleotopology”, Southwestern Cavers, VI (1967), 72–78

[4] Golovach P. A., “Equivalence of two formalizations of a search problem on a graph”, Vestnik Leningrad Univ. Math., 22:1 (1989), 13–19 | MR | Zbl

[5] Golovach P. A., “An extremal search problem on graphs”, Vestnik Leningrad Univ. Math., 23:3 (1990), 19–25 | MR | Zbl

[6] Golovach P. A., “Minimal trees of a given search number”, Cybernetics and Systems Analysis, 28:4 (1992), 509–513 | DOI | MR | Zbl

[7] Golovach P. A., Petrov N. N., Fomin F. V., “Search in graphs”, Proc. Steklov Inst. Math., 1, 2000, S90–S103 | MR | Zbl

[8] Fomin F. V., Thilikos D. M., “An annotated bibliography on guaranteed graph searching”, Theoret. Comp. Science, 399:3 (2008), 236–245 | DOI | MR | Zbl

[9] Parsons T. D., “Pursuit–evasion in a graph”, Theory and Applications of Graphs, 642, eds. Y. Alavi, D. R. Lick, Springer, Berlin, 1976, 426–441 | DOI | MR

[10] Petrov N. N., “A problem of pursuit in the absence of information on the pursued”, Differ. Uravn., 18:8 (1982), 1345–1352 (in Russian) | MR