Searching Symmetric Networks with Utilitarian-Postman Paths CDAM Research Report CDAM-2006-05
Steve Alpern, V. J. Baston, Gal Shmuel · 2006
For any network Q; one may consider the zero-sum search game (Q) in which the (minimizing) Searcher picks a unit speed path S (t) in Q; the Hider picks a pointH inQ; and the payo¤is the meeting time T = min ft : S (t) = Hg : We show rst that ifQ is symmetric (edge and vertex transitive), then it is optimal for the Hider to pickH uniformly inQ; so that the Searcher must follow a Utilitarian Postman path (one which minimizes the time to reach a random point). We then show that if Q is symmetric of odd degree, with n vertices and m unit length edges, the value V of (Q) satis es V m 2 + n 2n 8m ; with equality if and only if Q has a path v1; v2; : : : ; vn 1 of distinct vertices, such that the edge set Q [ 2)=2 i=1 (v2i; v2i+1) is connected.