Traversals of Infinite Graphs with Random Local Orientations

En savoir plus sur le livre

Focusing on graph exploration by autonomous agents, this monograph delves into various algorithms and introduces randomized versions, including randomized rotor routers and the random basic walk. It addresses the critical question of recurrence versus transience for the random basic walk on locally finite, bounded degree graphs. The work offers insights into exploratory behavior on finite graphs like lattices and complete graphs, supplemented by applications, examples, and open problems, making it a comprehensive resource for researchers in mathematics and computer science.