Design of cages with a randomized progressive edge-growth algorithm
Design of cages with a randomized progressive edge-growth algorithm
复制标题
DOI：
10.1109/lcomm.2008.071843
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
A. Venkiah;D. Declercq;C. Poulliat
中科院分区：
文献类型：
--
作者：
A. Venkiah;D. Declercq;C. Poulliat
渐进边生长(PEG)构造是一种构造具有良好围长性质的二部图的著名算法。在这封信中，我们提出了对聚乙二醇法的一些改进，这些改进极大地改善了所得到的图的围长性质：给定图的大小，它们增加了算法所能达到的周长g，当围长不能增加时，我们的改进算法最小化了长度为g的圈的数目。作为主要例证，我们主要关注规则的列权两图(dv=2)，尽管我们的算法可以应用于任何图的连通性。DV=2图类通常用于可被视为单部图的非二进制低密度奇偶校验码：对于给定的目标周长GT，该新的PEG算法实例允许构造笼子，即具有最小尺寸的图，使得存在周长GT的图，这是人们可能希望的最佳结果。
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.