DMTCS Proceedings, Automata 2010 - 16th Intl. Workshop on CA and DCS

Font Size:  Small  Medium  Large

60/102 Null Boundary Cellular Automata based expander graphs

S.-J. Cho, U.-S. Choi, H.-D. Kim, Y.-H. Hwang, J.-G. Kim

Abstract


Expander graphs are useful in the design and analysis of communication networks. Mukhopadhyay et al. introduced a method to generate a family of expander graphs based on nongroup two predecessor single attractor Cellular Automata(CA). In this paper we propose a method to generate a family of expander graphs based on 60/102 Null Boundary CA(NBCA) which is a group CA. The spectral gap generated by our method is maximal. Moreover, the spectral gap is larger than that of Mukhopadhyay et al.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional