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 -