Search

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers $\alpha $ , $\beta $ , and $\gamma $ , and degree sequences $\pi $ and $\pi '$ , the problem of determining whether there exists a simple bipartite graph with degree sequences $(\pi, \pi ')$ that has at most $\alpha $ ($\beta $ and $\gamma $) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence $\pi $ , a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is $\pi $ and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced. [ABSTRACT FROM AUTHOR]

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered. [ABSTRACT FROM AUTHOR]

Glass models are frequently used to model gene regulatory networks. A distinct feature of the Glass model is that its dynamics can be formalized as paths through multi-dimensional binary hypercubes. In this paper, we report a broad range of results about Glass models that have been obtained by computing the binary codes that correspond to the hypercube paths. Specifically, we propose algorithmic methods for the synthesis of specific Glass networks based on these codes. In contrast to existing work, bi-periodic networks and networks possessing both stable equilibria and periodic trajectories are considered. The robustness of the attractor is also addressed, which gives rise to hypercube paths with nondominated nodes and double coils. These paths correspond to novel combinatorial problems, for which initial experimental results are presented. Finally, a classification of Glass networks with respect to their corresponding gene interaction graphs for three genes is presented. [ABSTRACT FROM AUTHOR]

Let G = (u ∪ W, ϵ) be a bipartite graph with disjoint vertex sets U and W, edge set ϵ, and girth g. This correspondence presents an algorithm for counting the number of cycles of length g, g + 2, and g + 4 incident upon every vertex in U ∪ W. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as O(gn³) where n = max(∣U∣, ∣W∣). [ABSTRACT FROM AUTHOR]