Skip to Main content Skip to Navigation
Conference papers

60/102 Null Boundary Cellular Automata based expander graphs

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185496
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 2:16:44 PM
Last modification on : Tuesday, March 7, 2017 - 3:06:58 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:03:26 AM

File

dmAL0102.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185496, version 1

Collections

Citation

Sung-Jin Cho, Un-Sook Choi, Han-Doo Kim, Yoon-Hee Hwang, Jin-Gyoung Kim. 60/102 Null Boundary Cellular Automata based expander graphs. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. pp.19-28. ⟨hal-01185496⟩

Share

Metrics

Record views

133

Files downloads

777