| Article ID: | iaor20021354 |
| Country: | Germany |
| Volume: | 29 |
| Issue: | 4 |
| Start Page Number: | 533 |
| End Page Number: | 542 |
| Publication Date: | Jan 2000 |
| Journal: | International Journal of Game Theory |
| Authors: | Gal S. |
| Keywords: | graphs, search |
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).