Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Quasirandomness in Graphs

MPG-Autoren
/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44447

Friedrich,  Tobias
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Doerr, B., & Friedrich, T. (2006). Quasirandomness in Graphs. Electronic Notes in Discrete Mathematics, 25, 61-64.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0019-E37D-9
Zusammenfassung
Jim Propp�s rotor router model is a simple deterministic analogue of a random walk. Instead of distributing chips randomly, it serves the neighbors in a fixed order. We analyze the difference between Propp machine and random walk on the infinite two- dimensional grid. We show that, independent of the starting configuration, at each time, the number of chips on each vertex deviates from the expected number of chips in the random walk model by at most a constant c, which is 7.83 for clockwise rotor sequences and 7.28 otherwise. This is the first paper which demonstrates that the order in which the neighbors are served makes a difference.