TY - GEN

T1 - Random walks and bisections in random circulant graphs

AU - Mans, Bernard

AU - Shparlinski, Igor E.

PY - 2012

Y1 - 2012

N2 - Using number theoretical tools, we prove two main results for random r-regular circulant graphs with n vertices, when n is sufficiently large and r is fixed. First, for any fixed ε > 0, prime n and L ≥ n 1/r (logn) 1+1/r+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm to find a vertex bisector and an edge bisector, both of size less than n 1-1/r+o(1). As circulant graphs are popular network topologies in distributed computing, we show that our results can be exploited for various information dissemination schemes. In particular, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. This settles an open question in an earlier work of the authors (2004) and shows that the generic gossiping algorithms of that work are nearly optimal.

AB - Using number theoretical tools, we prove two main results for random r-regular circulant graphs with n vertices, when n is sufficiently large and r is fixed. First, for any fixed ε > 0, prime n and L ≥ n 1/r (logn) 1+1/r+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm to find a vertex bisector and an edge bisector, both of size less than n 1-1/r+o(1). As circulant graphs are popular network topologies in distributed computing, we show that our results can be exploited for various information dissemination schemes. In particular, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. This settles an open question in an earlier work of the authors (2004) and shows that the generic gossiping algorithms of that work are nearly optimal.

UR - http://www.scopus.com/inward/record.url?scp=84860826228&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-29344-3_46

DO - 10.1007/978-3-642-29344-3_46

M3 - Conference proceeding contribution

AN - SCOPUS:84860826228

SN - 9783642293436

VL - 7256

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 542

EP - 555

BT - LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings

A2 - Fernández-Baca, David

PB - Springer, Springer Nature

CY - Heidelberg

T2 - 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012

Y2 - 16 April 2012 through 20 April 2012

ER -