BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jared Howell appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
The watchman's walk problem in a digraph calls for finding a minimum length closed dominating walk, where direction of arcs is respected. The watchman's walk of a de Bruijn graph of order $k$ is described by a de Bruijn sequence of order $k-1$. This idea is extended to certain subdigraphs of de Bruijn graphs.
Suppose we have a network that is represented by a graph $G$. Potentially a fire (or other type of contagion) might erupt at some vertex of $G$. We are able to respond to this outbreak by establishing a firebreak at $k$ other vertices of $G$, so that the fire cannot pass through these fortified vertices. The question that now arises is which $k$ vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the $k$ vertices of the firebreak. This is the essence of the {\sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.
In a graph, a watchman's walk is a minimum closed dominating walk. Given a graph $G$ and a single watchman, the length of a watchman's walk in $G$ (the watchman number) is denoted by $w(G)$ and the typical goals of the watchman's walk problem is to determine $w(G)$ and find a watchman's walk in $G$. In this paper, we extend the watchman's walk problem to directed graphs. In a directed graph, we say that the watchman can only move to and see the vertices that are adjacent to him relative to outgoing arcs. That is, a watchman's walk is oriented and domination occurs in the direction of the arcs. The directed graphs this paper focuses on are families of tournaments and orientations of complete multipartite graphs. We give bounds on the watchman number and discuss its relationship to variants of the domination number.