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.

[img] [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)


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.

Item Type: Thesis (Masters)
Item ID: 9013
Additional Information: Includes bibliographical references.
Department(s): Science, Faculty of > Mathematics and Statistics
Date: 2009
Date Type: Submission
Library of Congress Subject Heading: Domination (Graph theory) -- Watchmen

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics