Results 21 to 30 of about 789,258 (121)
A Message-Passing Algorithm for Counting Short Cycles in a Graph
, 2010 A message-passing algorithm for counting short cycles in a graph is presented. For bipartite graphs, which are of particular interest in coding, the algorithm is capable of counting cycles of length g, g +2,..., 2g - 2, where g is the girth of the graph.
Banihashemi, Amir H., Karimi, Mehdi
core +1 more source
Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights [PDF]
, 2005 We present a tree-based construction of LDPC codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding.
Kelley, Christine +2 more
core +4 more sources
Some spectral and quasi-spectral characterizations of distance-regular graphs [PDF]
, 2016 © . This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/In this paper we consider the concept of preintersection numbers of a graph.
Abiad, Aida +2 more
core +2 more sources
On Unicyclic Graphs with Minimum Graovac–Ghorbani Index
MathematicsIn discrete mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Snježana Majstorović Ergotić
doaj +1 more source
Necessary and Sufficient Girth Conditions for LDPC Tanner Graphs with Denser Protographs [PDF]
arXiv, 2021 This paper gives necessary and sufficient conditions for the Tanner graph of a quasi-cyclic (QC) low-density parity-check (LDPC) code based on the all-one protograph to have girth 6, 8, 10, and 12, respectively, in the case of parity-check matrices with column weight 4.
arxiv
Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth [PDF]
, 2018 The girth of a graph is the length of its shortest cycle. Due to its relevance in graph theory, network analysis and practical fields such as distributed computing, girth-related problems have been object of attention in both past and recent literature. In this paper, we consider the problem of listing connected subgraphs with bounded girth. As a large
arxiv +1 more source
Error Correction Capability of Column-Weight-Three LDPC Codes: Part II
, 2008 The relation between the girth and the error correction capability of column-weight-three LDPC codes is investigated. Specifically, it is shown that the Gallager A algorithm can correct $g/2-1$ errors in $g/2$ iterations on a Tanner graph of girth $g ...
Chilappagari, Shashi Kiran +3 more
core +1 more source
Generation of cubic graphs and snarks with large girth [PDF]
, 2017 We describe two new algorithms for the generation of all non-isomorphic cubic graphs with girth at least $k\ge 5$ which are very efficient for $5\le k \le 7$ and show how these algorithms can be efficiently restricted to generate snarks with girth at ...
Brinkmann, Gunnar, Goedgebeur, Jan
core +1 more source
On the structure of graphs with given odd girth and large minimum degree [PDF]
J. Graph Theory 80 (2015), no. 1, 69-81, 2016 We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andr\'asfai, Erd\H os, and S\'os implies that every $n$-vertex graph with odd girth $2k+1$ and minimum degree bigger than $\frac{2}{2k+1}n$ must be bipartite.
arxiv +1 more source
On the diversity of test instances for studying branch‐and‐bound performance
Australian &New Zealand Journal of Statistics, EarlyView.Summary In their paper ‘An Automatic Method for Solving Discrete Programming Problems’, Ailsa Land and Alison Doig developed a branch‐and‐bound method for solving the general case of the mixed integer linear programming (MIP) problem. A core part of the algorithm, branch variable selection, has received renewed attention in recent years with the ...
Simon Bowly, Kate Smith‐Miles
wiley +1 more source