Description

In mathematics and computer science, many systems of individuals and the relationships between them may be modeled as graphs. It is natural to consider the problem of graph exploration by an autonomous agent, e.g. an individual meeting members of a social network, a webcrawler exploring the web, optimizing protein folding by exploring the graph of allowable shapes, software moving on a network of computers, or the Mars rover exploring the terrain of Mars. This monograph compares numerous exploration algorithms, and introduces randomized versions of existing exploration algorithms including randomized rotor routers and the random basic walk. The question of recurrence vs. transience is settled for the random basic walk on the class of locally finite, bounded degree graphs, and this theory specializes to give bounds on the exploratory behavior of the random basic walk on finite graphs such as lattices and complete graphs. Applications, examples, and open problems are provided throughout the text.