Bisecting and gossiping in circulant graphs

Bernard Mans*, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

Circulant graphs are popular network topologies that arise in distributed computing. In this paper, we show that, for circulant graphs, a simple condition for isomorphism, combined with lattices reduction algorithms, can be used to develop efficient distributed algorithms. We improve the known upper bounds on the vertex-bisection (respectively the edge-bisection) width of circulant graphs. Our method is novel and provides a polynomial-time algorithm to partition the set of vertices (respectively the set of edges) to obtain these bounds and the respective sets. By exploiting the knowledge of the bisection width of this topology, we introduce generic distributed algorithms to solve the gossip problem in these networks. We present lower and upper bounds of the number of rounds in the vertex-disjoint and the edge-disjoint paths communication models when the number of nodes is prime.

Original languageEnglish
Pages (from-to)589-598
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2976
Publication statusPublished - 2004

Fingerprint

Dive into the research topics of 'Bisecting and gossiping in circulant graphs'. Together they form a unique fingerprint.

Cite this