Algorithms for generation of Ramanujan graphs, other Expanders and related LDPC codes

Monika Polak, Vasyl Ustimenko

Abstract


Expander graphs are highly connected sparse finite graphs. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. For practical applications it is very important to construct expander and Ramanujan graphs with given regularity and order. In general, constructions of the best expander graphs with a given regularity and order is no easy task. In this paper we present algorithms for generation of Ramanujan graphs and other expanders. We describe properties of obtained graphs in comparison to previously known results. We present a method to obtain a new examples of irregular LDPC codes based on described graphs and we briefly describe properties of this codes.

Full Text:

PDF


DOI: http://dx.doi.org/10.17951/ai.2015.15.2.14-21
Date of publication: 2015-10-11 00:00:00
Date of submission: 2016-04-28 09:13:32


Statistics


Total abstract view - 545
Downloads (from 2020-06-17) - PDF - 0

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.