Paper Info
Title
Improved message-passing algorithm for counting short cycles in bipartite graphs
Abstract
Recently, Karimi and Banihashemi proposed an algorithm based on message-passing to count cycles in a graph of lengths less than double its girth. The algorithm uses only integer additions and subtractions to compute messages at the nodes of the graph that are passed to adjacent nodes. The complexity of the algorithm, when applied to a bipartite graph of girth g that has E edges, is O(gE2). The algorithm is superior to many other existing algorithms in the literature. In this paper, an improvement of this algorithm is presented that cuts both the complexity and the computing time by a factor of two. The improved algorithm is also applied to Tanner graphs of quasi-cyclic codes and, in this case, the complexity can be further cut by a factor of p, where p is the size of the circulants in the parity-check matrix of the quasi-cyclic code.
Year
DOI
Venue
2015
10.1109/ISIT.2015.7282488
ISIT
Keywords
Field
DocType
Bipartite graph, Counting cycles, LDPC code, Message-passing algorithm, Tanner graph
Factor graph,Discrete mathematics,Combinatorics,Line graph,Folded cube graph,Computer science,Bipartite graph,Algorithm,Matching (graph theory),Tanner graph,Triangle-free graph,Blossom algorithm
Conference
Citations 
PageRank 
References 
2
0.43
6
Authors
3
Name
Order
Citations
PageRank
Juane Li1435.68
Shu Lin298572.16
Khaled A. S. Abdel-Ghaffar3616122.03