Cayley Graphs as an Underlying Network Structure

The design of computer networks and parallel processor configurations is a topic of increasing importance. Network designs which efficiently support communications between nodes are crucial for many applications. Cost and physical limitations generally prevent the nodes in a network from having more than a fixed number of hardware connections to other nodes (that is, the nodes must have bounded degree). This fundamental constraint makes the design problem nontrivial. The topic of interest is an explanation of ways in which group theory can be used to design bounded-degree communication-efficient networks. Our methods have yielded a number of network designs that are the largest known for networks satisfying specified bounds on node degree and either diameter or broadcast time, for values of these parameters that are in the range of potential engineering significance.

Francesc Comellas has an on-line degree/diameter table with information about the current largest known undirected graphs.

Also see the various network design tables at the http://moorebound.indstate.edu wiki.

An old table of the best-known (degree,time) broadcast graphs.

Michael J. Dinneen, Algebraic Methods for Efficient Network Construction , Master's Thesis, Department of Computer Science, University of Victoria, Victoria, B. C., Canada, 1991.

Michael J. Dinneen, Vance Faber, and Michael R. Fellows, ``Algebraic constructions of efficient broadcast networks'' , In H. F. Mattson, T. Mora, and T. R. N. Rao, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes , volume 539 of Lecture Notes in Computer Science, pages 150-158. Springer-Verlag, October 1991.

Lowell Campbell, Gunnar E. Carlsson, Michael J. Dinneen, Vance Faber, Michael R. Fellows, Michael A. Langston, James W. Moore, Andrew P. Mullhaupt, and Harlan B. Sexton, ``Small diameter symmetric networks from linear groups'' , IEEE Transactions on Computers , 41 (1992) 218-220.

Michael J. Dinneen, ``The Complexity of Broadcasting in Bounded-Degree Networks'' , Los Alamos National Laboratory manuscript LACES-[05C-94-31], 1992. (http://arxiv.org/abs/math/9411222)

Michael J. Dinneen and Paul R. Hafner, ``New results for the degree/diameter problem'' , Networks, volume 24, pages 359-367, October 1994.

Three recent papers, two of which use compound methods, for construction broadcast networks are given below:

Michael J. Dinneen, Jose A. Ventura, Mark C. Wilson and Golbon Zakeri, ``Compound Constructions of Minimal Broadcast Networks'', Discrete Applied Math 93, 205--232 (1999).

Michael J. Dinneen, Jose A. Ventura, Mark C. Wilson and Golbon Zakeri, ``Construction of Time-Relaxed Minimal Broadcast Networks'', to appear Parallel Processing Letters (1998). (previous version: Department of Computer Science Technical Report TR139, University of Auckland, New Zealand, 1997.)

Michael J. Dinneen, Geoffrey Pritchard and Mark C. Wilson, ``Degree- and Time- Constrained Broadcast Networks'', University of Auckland Report {CDMTCS}-080, 1998.
[Also in Networks 39(3), 121--129, 2002.]

Michael J. Dinneen and Nian (Alfred) Zhou. ``An Optimal Family of Directed, Bounded-Degree Broadcast Networks'', In CATS'03 conference, ENTCS, Vol 78, Feb 2003.

A survey paper on some recent network design work appear in:

Michael J. Dinneen. ``Group-theoretic methods for designing networks'', Bulletin of the European Associaton for Theoretical Computer Science, 65:53--61, June 1998. (News from New Zealand)

The study of update networks are presented in the following papers.

Michael J. Dinneen and Bakh Khoussainov, ``Update Games and Update Networks'' , Journal of Discrete Algorithms,. 2(1), 55--68, 2002 (also CDMTCS-105).

Michael J. Dinneen and Bakh Khoussainov, ``Update Networks and Their Routing Strategies'' , in Research Report CDMTCS-127, 2000.

Hans L. Bodlaender, Michael J. Dinneen and Bakh Khoussainov, ``On Game-Theoretic Models of Networks'' (Relaxed Update and Partition Network Games) , ISAAC'01, Dec 2001.