Implementing efficient copwin strategies on copwin graphs
LE3 .A278 2006
2006
Diamond, Jim Clarke, Nancy
Acadia University
Bachelor of Science
Honours
Computer Science
The game of cops and robber is a pursuit game played on a reflexive graph. This game has gained a lot of research interest recently due to its applications such as searching for intruders on the Internet. This thesis summarizes the characterization of copwin graphs and investigates different approaches for the copwin strategies. The objective of this thesis is to develop some efficient copwin strategies on copwin graphs. In addition, we have implemented and compared three different copwin strategies, including optimal graph searching techniques, graph retraction mapping, and a combination of both graph searching and retracting techniques. vi
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.
https://scholar.acadiau.ca/islandora/object/theses:506