Approximating the position of a hidden agent in a graph

arXiv1805.04386MaRDI QIDQ6301467FDOQ6301467

Authors: Hannah Guggiari, Alexander Roberts, Alex Scott

Publication date: 11 May 2018

Abstract: A cat and mouse play a pursuit and evasion game on a connected graph

G

with

n

vertices. The mouse moves to vertices

m_{1}, m_{2}, d o t s

of

G

where

m_{i}

is in the closed neighbourhood of

m_{i - 1}

for

i g e q 2

. The cat tests vertices

c_{1}, c_{2}, d o t s

of

G

without restriction and is told whether the distance between

c_{i}

and

m_{i}

is at most the distance between

c_{i - 1}

and

m_{i - 1}

. The mouse knows the cat's strategy, but the cat does not know the mouse's strategy. We will show that the cat can determine the position of the mouse up to distance

O (s q r t n)

within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach.

This page was built for publication: Approximating the position of a hidden agent in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301467)