The Watchman's walk problem and its variations

Keeping, Rebecca (2009) The Watchman's walk problem and its variations. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (3MB)

Abstract

Given a graph and a single watchman, the Watchman’s Walk Problem is concerned with finding closed dominating walks of minimum length, which the watchman can traverse to efficiently guard the graph. When multiple guards are available, two natural variations emerge: (1) given a fixed number of guards, how can we minimize the length of time for which vertices are unobserved? and (2) given fixed time constraints on the monitoring of vertices, what is the minimum number of guards required? The present thesis reviews known results for the original problem as well as its variations, and proves an upper bound on the number of guards required when time is fixed.

Actions (login required)

View Item