The watchman's walk problem on directed graphs

Pittman, Brittany (2020) The watchman's walk problem on directed graphs. 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 (465kB)

Abstract

A watchman’s walk in a graph is a minimum closed dominating walk. Given a graph and a single watchman, the aim of the Watchman’s walk problem is to find a shortest closed walk that allows the guard to efficiently monitor all vertices in the graph. In a directed graph, a watchman’s walk must obey the direction of the arcs. In this case, we say that the guard can only move to and see the vertices that are adjacent to him relative to outgoing arcs. In this thesis, we consider the watchman’s walk problem on directed graphs. In particular, we study the problem on tournaments, orientations of complete bipartite and multipartite graphs, and directed graphs formed from sequences.

Actions (login required)

View Item