Discrete Math Seminar: Abbas Mehrabian
Topic
Cops and a Fast Robber on Planar and Random Graphs
Speakers
Details
We study a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let c(G) denote the number of cops needed to capture the robber in a graph G, and let tw(G) denote the treewidth of G. We show that if G is planar then c(G) = Theta(tw(G)), and there is a polynomial-time constant-factor approximation algorithm for computing c(G). We also determine, up to constant factors, the value of c(G) of the random graph G(n,p) for all admissible values of p, and show that when the average degree goes to infinity, c(G) is typically asymptotic to the domination number.
This is joint work with Noga Alon.
Additional Information
Location: ESB 4127
Abbas Mehrabian, UBC and SFU
Abbas Mehrabian, UBC and SFU
This is a Past Event
Event Type
Scientific, Seminar
Date
October 27, 2015
Time
-
Location