Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Doerr, Benjamin
Friedrich, Tobias

dblp
dblp



BibTeX cite key*:

2006CTW_Propp

Title

Title*:

Quasirandomness in Graphs

Journal

Journal Title*:

Electronic Notes in Discrete Mathematics

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75GV-4KGFWY1-K-1&_cdi=13104&_user=43521&_orig=search&_coverDate=08%2F01%2F2006&_sk=999749999&view=c&wchp=dGLbVtb-zSkzS&md5=22c9146de666c351cb45ca14297ebf82&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

1571-0653

Vol, No, pp, Date

Volume*:

25

Number:


Publishing Date:

2006

Pages*:

61-64

Number of
VG Pages:

6

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B75GV-4KGFWY1-K&_user=43521&_coverDate=08%2F01%2F2006&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=8b32f6b90f819e35a7995fe1a21243c0

Categories,
Keywords:

Random walk, Quasirandomness

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{2006CTW_Propp,
AUTHOR = {Doerr, Benjamin and Friedrich, Tobias},
TITLE = {Quasirandomness in Graphs},
JOURNAL = {Electronic Notes in Discrete Mathematics},
PUBLISHER = {Elsevier},
YEAR = {2006},
VOLUME = {25},
PAGES = {61--64},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {1571-0653},
}


Entry last modified by Benjamin Doerr, 07/09/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/02/2007 02:39:06 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Benjamin Doerr
Christine Kiesel
Christine Kiesel
Mathias Bader
Mathias Bader
Edit Dates
01/10/2008 03:31:24 PM
22.06.2007 07:57:44
22.06.2007 07:57:02
27.01.2007 19:08:19
27.01.2007 19:07:40