Technical Report CIS-2009-02

TR#:CIS-2009-02
Class:CIS
Title: Efficiently Patrolling Hamiltonian and Two-Connected Graphs
Authors: Yotam Elor and Alfred M. Bruckstein.
PDFCIS-2009-02.pdf
Abstract: We present two probabilistic patrolling strategies for a single agent patrolling an undirected graph. A single ant-like agent with very low capabilities is considered, the agent have small memory and he can sense only its neighborhood. However, he may mark the graph vertices with pheromone stamps which can later be sensed. These markings are used as a primitive form of distributed memory. The first algorithm presented is designed to patrol Hamiltonian graphs. By executing the proposed algorithm, the agent finds a Hamilton cycle and follows it. By following the cycle, the agent performs an optimal patrol. The second algorithm we present aims to patrol graphs whose square is Hamiltonian. Using the algorithm, the agent finds a cycle of length at most 2|G| and follows it. The maximum time lag between two successive visits to any vertex using the proposed strategy is at most twice the optimal so the patrol quality is at least half the optimal.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2009/CIS/CIS-2009-02), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2009
To the main CS technical reports page

Computer science department, Technion
admin