Keeping, Rebecca (2009) The Watchman's walk problem and its variations. Masters thesis, Memorial University of Newfoundland.
- 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.
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)|
|Additional Information:||Includes bibliographical references.|
|Department(s):||Science, Faculty of > Mathematics and Statistics|
|Library of Congress Subject Heading:||Domination (Graph theory) -- Watchmen|
Actions (login required)