David White

Traversals of Infinite Graphs with Random Local Orientations

• Broschiertes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: LAP Lambert Academic Publishing
• Seitenzahl: 84
• Erscheinungstermin: 27. August 2015
• Englisch
• Abmessung: 220mm x 150mm x 6mm
• Gewicht: 143g
• ISBN-13: 9783659776878
• ISBN-10: 3659776874
• Artikelnr.: 43757572

Autorenporträt

David White is an Assistant Professor at Denison University, in Granville, Ohio. He received degrees in mathematics and computer science from Wesleyan University, focusing in abstract algebraic topology and discrete applied mathematics, respectively. He grew up in Chicago, received his BA from Bowdoin College, and is an avid traveler.