Cops, robber, and photo radar.

Abstract

A b stra ctT h is gam e is a m ix tu re of S earch in g an d C op s an d R ob b er. T h eC op s h ave p artial in form ation p rov id ed b y sen sin g d ev ices calledp h oto rad ar. T h e R ob b er h as p erfect in form ation . W e give b ou n d son th e n u m b er of p h oto rad ar u n its req u ired b y on e C op to cap tu rea R ob b er on a tree an d , w ith less tigh t b ou n d s, on a cop w in grap h .