University of Cambridge > > Combinatorics Seminar > Searching for hidden moving targets on graphs

Searching for hidden moving targets on graphs

Add to your list(s) Download to your calendar using vCal

  • UserJohn Haslegrave (University of Sheffield)
  • ClockThursday 21 May 2015, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

We consider two closely related games where an invisible target moves around a graph and a searcher probes vertices trying to discover its location. For the first game we give a classification of graphs where the searcher can guarantee to succeed in bounded time. For the second, introduced by Seager, the searcher gets distance information from each probe. Carraher, Choi, Delcourt, Erickson and West showed that if each edge of a graph on n vertices is subdivided m times, where m>=n, the searcher wins, and conjectured that this is best possible for complete graphs. We show that this is not the case, obtaining an exact threshold of n/2 for complete graphs (except for four small values of n), and also give an exact threshold for complete r-partite graphs. Results for the second game are joint work with Richard Johnson (Memphis) and Sebastian Koch (Cambridge).

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity