60/102 Null Boundary Cellular Automata based expander graphs

Sung-Jin Cho 1 Un-Sook Choi 2 Han-Doo Kim 3 Yoon-Hee Hwang 1 Jin-Gyoung Kim 1
1 Department of Applied Mathematics
2 Department of Media Engineering
3 School of Computer Aided Science
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.
Keywords : Expander graphs 60/102 NBCA Spectral gaps Bipartite graphs Eigenvalue.
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.19-28, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01185496
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:44
Dernière modification le : mardi 7 mars 2017 - 15:06:58
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:03:26

Fichier

dmAL0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185496, version 1

Collections

INSMI | TDS-MACS

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. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.19-28, 2010, DMTCS Proceedings. 〈hal-01185496〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

154

Contact


archive-ouverte@inria.fr