Design of cages with a randomized progressive edge-growth algorithm

Abstract

The progressive edge-growth (PEG) construction is a well known algorithm for constructing bipartite graphs with good girth properties. In this letter, we propose some improvements in the PEG algorithm which greatly improve the girth properties of the resulting graphs: given a graph size, they increase the girth g achievable by the algorithm, and when the girth cannot be increased, our modified algorithm minimizes the number of cycles of length g. As a main illustration, we focus on regular column-weight two graphs (d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">v</sub> = 2), although our algorithm can be applied to any graph connectivity. The class of d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">v</sub> = 2 graphs is often used for non-binary low density parity check codes that can be seen as monopartite graphs: for a given target girth g <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sub> , this new instance of the PEG algorithm allows to construct cages, i.e. graphs with the minimal size such that a graph of girth g <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sub> exists, which is the best result one might hope for.