On the optimality of a simple strategy for searching graphs

Consider a search game with an immobile hider in a graph. A Chinese postman tour is a closed trajectory which visits all the points of the graph and has minimal length. We show that encircling the Chinese postman tour in a random direction is an optimal search strategy if and only if the graph is weakly Eulerian (i.e it consists of several Eulerian curves connected in a tree-like structure).

MoreLess

Year of publication:	2001-05-04
Authors:	Gal, Shmuel
Published in:	International Journal of Game Theory. - Springer. - Vol. 29.2001, 4, p. 533-542
Publisher:	Springer
Subject:	Search game \| weakly Eulerian graph \| weakly cyclic graph \| Chinese postman tour

More details

Extent:	application/pdf
Type of publication:	Article
Notes:	Received: December 1999/Revised version: September 2000
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005755790