Design of cages with a randomized progressive edge-growth algorithm

摘要

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 (dv = 2), although our algorithm can be applied to any graph connectivity. The class of dv = 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 gt, this new instance of the PEG algorithm allows to construct cages, i.e. graphs with the minimal size such that a graph of girth gt exists, which is the best result one might hope for.