The Watchman's walk problem and its variations

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.