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

Search Nedrilad ::

Custom Search