Game Development Reference
In-Depth Information
graph - and also to decompositions of graphs. As we will see below, for
the node searching game considered above this is indeed the case. The first
monotonicity proof, for the edge searching variant, was given by LaPaugh
[1993] and since then monotonicity has been established for a wide range of
graph searching games.
Monotonicity of graph searching games will play an important part of this
chapter and we will explore this in detail in Section 7.4.
Applications
The goal of graph searching games is to devise a winning strategy for the
searchers that uses as few searchers as possible. The minimal number of
searchers needed to guarantee capture of the fugitive on a particular graph
thereby yields a complexity measure for the graph, which we call the search
width . This measure, obviously, depends on the type of game being considered.
The search width of a graph measures the connectivity of a graph in some way
and it is therefore not surprising that there is a close relationship between
width measures defined by graph searching games and other complexity or
width measures for graphs studied in the literature, such as the tree-width
or the path-width of a graph. This connection is one of the driving forces
behind graph searching games and we will explore it in Section 7.6 below.
Graph searching games have found numerous applications in computer
science. One obvious application of graph searching games is to all kinds of
search problems and the design of optimal search strategies. In games with
an invisible fugitive, searching can also be seen as conquering and an optimal
search strategy in this context is a strategy to conquer a country so that at
each point of time the number of troops needed to hold the conquered area
is minimised.
Furthermore, graph searching games have applications in robotics and the
planning of robot movements, as it is explored, for instance, by Guibas et al.
[1996]. Another example of this type is the use of graph searching games
to network safety as explored by Franklin et al. [2000] where the fugitive
models some information and the searchers model intruders, or infected
computers, trying to learn this information. The goal here is not to design
an optimal search strategy but to improve the network to increase the search
number. Graph searching games have also found applications in the study of
sequential computation through a translation from pebbling games. We will
give more details in Section 7.3.2.
Other forms of graph searching games are closely related to questions
in logic. For instance the entanglement of a graph is closely related to