English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Counting short cycles in bipartite graphs is a fundamental problem ofinterest in many fields including the analysis and design of low-densityparity-check (LDPC) codes. There are two computational approaches to countshort cycles (with length smaller than $2g$, where $g$ is the girth of thegraph) in bipartite graphs. The first approach is applicable to a general(irregular) bipartite graph, and uses the spectrum $\{\eta_i\}$ of the directededge matrix of the graph to compute the multiplicity $N_k$ of $k$-cycles with$k < 2g$ through the simple equation $N_k = \sum_i \eta_i^k/(2k)$. Thisapproach has a computational complexity $\mathcal{O}(|E|^3)$, where $|E|$ isnumber of edges in the graph. The second approach is only applicable tobi-regular bipartite graphs, and uses the spectrum $\{\lambda_i\}$ of theadjacency matrix (graph spectrum) and the degree sequences of the graph tocompute $N_k$. The complexity of this approach is $\mathcal{O}(|V|^3)$, where$|V|$ is number of nodes in the graph. This complexity is less than that of thefirst approach, but the equations involved in the computations of the secondapproach are very tedious, particularly for $k \geq g+6$. In this paper, weestablish an analytical relationship between the two spectra $\{\eta_i\}$ and$\{\lambda_i\}$ for bi-regular bipartite graphs. Through this relationship, theformer spectrum can be derived from the latter through simple equations. Thisallows the computation of $N_k$ using $N_k = \sum_i \eta_i^k/(2k)$ but with acomplexity of $\mathcal{O}(|V|^3)$ rather than $\mathcal{O}(|E|^3)$.

On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix