Search

Mixed graphs have both directed and undirected edges. We consider mixed graphs that are regular in both directed and undirected degree and with given girth. Araujo-Pardo, Hern'andez-Cruz, andMontellano-Ballesteros recently established a lower bound for regular mixed graphs with directed degree one that generalizes the Moore bound. In this paper we show that, in at least one non-trivial case, their bound can be achieved. For a few other specific values of direct degree, undirected degree and girth we are able to identify graphs (mixed cages) of minimum possible order. We also obtain some fairly tight bounds for a few other cases. [ABSTRACT FROM AUTHOR]

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]

In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with $|V|$ nodes and girth $g$ , our technique has a time complexity of $\mathcal {O}(|V|^{2}\Delta)$ to count $g$ -cycles and $(g+2)$ -cycles, and a time complexity of $\mathcal {O}(|V|^{2}\Delta ^{2})$ to count $(g+4)$ -cycles, where $\Delta $ is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to $\mathcal {O}(|V|^{2}\Delta)$. Compared to the fastest known algorithm, which has a complexity $\mathcal {O}(g |V|^{2} \Delta ^{2})$ , the proposed method always has a lower complexity for counting $g$ -cycles and $(g+2)$ -cycles. It also has a lower complexity for counting $(g+4)$ -cycles in bi-regular graphs and in scenarios where $g$ is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than $\mathcal {O}\left({|V|^{2-\frac {2}{1+i}}}\right)$ that can determine whether a given sparse bipartite graph has a cycle of length $4i$. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes. [ABSTRACT FROM AUTHOR]

In this paper, we give lower bounds on the size of $(a,b)$ elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, $g$ , and irregular ones with girth 8, where $a$ is the size and $b$ is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of $g$ and $b$ , based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables $a$ , $b$ , $\gamma $ , and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of {2, 3, 4, 5, 6} and fulfill the inequality $(b/a)<1$. Moreover, we present a range of numerical results about $(a,b)$ ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature. [ABSTRACT FROM AUTHOR]

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ). [ABSTRACT FROM AUTHOR]

In this paper, we deal with time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs). Classic design approaches usually start from quasi-cyclic low-density parity-check block codes and exploit suitable unwrapping procedures to obtain SC-LDPC-CCs. We show that the direct design of the SC-LDPC-CCs syndrome former matrix or, equivalently, the symbolic parity-check matrix, leads to codes with smaller syndrome former constraint lengths with respect to the best solutions available in the literature. We provide theoretical lower bounds on the syndrome former constraint length for the most relevant families of SC-LDPC-CCs, under constraints on the minimum length of cycles in their Tanner graphs. We also propose new code design techniques that approach or achieve such theoretical limits. [ABSTRACT FROM PUBLISHER]

High-rate low-density parity-check (LDPC) codes are the focus of intense research in magnetic recording because, when decoded by the iterative sum-product algorithm, they show decoding performance close to the Shannon capacity. However, cycles, especially short cycles, are harmful to LDPC codes. The paper describes the partition-and-shift LDPC (PS-LDPC) codes, a new class of regular, structured LDPC codes that can be designed with large girth and arbitrary large minimum distance. Large girth leads to more efficient iterative decoding and codes with better error-floor properties than random LDPC codes. PS-LDPC codes can be designed for any desired column weight and with flexible code rates. The paper details the girth and distance properties of the codes and their systematic construction and presents analytical and simulation performance results that show that, in the high signal-to-noise ratio region, PS-LDPC codes out- perform random codes, alleviating the error floor phenomenon. [ABSTRACT FROM AUTHOR]

A vertex subset C of a connected graph G is called a connected k -path vertex cover ( C V C P k ) if every path on k vertices contains at least one vertex from C , and the subgraph of G induced by C is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) C V C P k problem. We first show that the minimum weight C V C P k problem can be solved in time O ( n ) when the graph is a tree, and can be solved in time O ( r n ) when the graph is a uni-cyclic graph whose unique cycle has length r , where n is the number of vertices. Making use of the algorithm on trees, we present a k -approximation algorithm for the minimum (cardinality) C V C P k problem under the assumption that the graph has girth at least k . An example is given showing that performance ratio k is asymptotically tight for our algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the construction of a type of quasi-cyclic low-density-parity-check (QC LDPC) codes called cycle codes. Based on our previous work, the maximum cycle entropy (MCE) algorithm for constructing nonbinary LDPC codes can be extended to its QC form (QC-MCE), which maintains the QC structure of the parity-check matrix. With this method employed, an elegant distribution of nonzero entries over the Galois field GF(q) can be obtained among the cycles whose length is related to the girth. Thus, the independence of probabilistic information transferred during decoding is increased, leading to a better performance. Extensive simulation results show that the proposed QC-MCE algorithm behaves much better than the conventional random one and performs as well as the existing method over a pattern media channel with both additive white Gaussian noise (AWGN) and transition jitter noise (TJN). The decoding complexity of our proposed codes is reasonably low due to the QC structure of the codes. The codes constructed with the proposed method can be well applied over the patterned media storage. [ABSTRACT FROM AUTHOR]