Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Quasirandomness in Graphs

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

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Doerr, Benjamin1, Autor           
Friedrich, Tobias1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: 2006CTW_Propp
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Electronic Notes in Discrete Mathematics
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Ams : North-Holland
Seiten: - Band / Heft: 25 Artikelnummer: - Start- / Endseite: 61 - 64 Identifikator: ISSN: 1571-0653
CoNE: https://pure.mpg.de/cone/journals/resource/111087903009000