Approximately locating an invisible agent in a graph with relative distance queries

作者：Dayanikli Dennis; Rautenbach Dieter^*

来源：Discrete Mathematics, 2018, 341(8): 2302-2307.

DOI：10.1016/j.disc.2018.05.006

• Pursuit and evasion game

In a pursuit evasion game on a finite, simple, undirected, and connected graph G, a first player visits vertices m(1), m(2),... of G, where m(i+1) is in the closed neighborhood of m(1) for every i, and a second player probes arbitrary vertices c(1), c(2),... of G, and learns whether or not the distance between c(i+1) and m(i+1) is at most the distance between c(i) and m(i). Up to what distance d can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that d is bounded by a constant. We conjecture that d = 0(log n) for every graph G of order n, and show that d = 0 if m(i+1) may differ from in, only if i is a multiple of some sufficiently large integer.

• 出版日期2018-8