An algorithm for counting short cycles in bipartite graphs

被引：56
作者：
Halford, TR [1 ]
Chugg, KM [1 ]
机构：
[1] Univ So Calif, Inst Commun Sci, Los Angeles, CA 90089 USA
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2006年 / 52卷 / 01期
关键词：
bipartite graphs; cycles; girth; graphical models of codes; loops;
D O I：
10.1109/TIT.2005.860472
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Let G = (U boolean OR W, epsilon) be a bipartite graph with disjoint vertex sets U and W, edge set epsilon, 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 boolean OR W. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as O(gn(3)) where n. = max(vertical bar U vertical bar, vertical bar W vertical bar).
引用
收藏
页码：287 / 292
页数：6
相关论文
共 50 条
  • [11] Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles
    Dehghan, Ali
    Banihashemi, Amir H.
    [J]. GRAPHS AND COMBINATORICS, 2019, 35 (06) : 1673 - 1693
  • [12] Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles
    Ali Dehghan
    Amir H. Banihashemi
    [J]. Graphs and Combinatorics, 2019, 35 : 1673 - 1693
  • [13] Null decomposition of bipartite graphs without cycles of length 0 modulo 4
    Jaume, Daniel A.
    Molina, Gonzalo
    Pastine, Adrian
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 614 (614) : 176 - 196
  • [14] Counting Unlabeled Bipartite Graphs Using Polya's Theorem
    Atmaca, Abdullah
    Oruc, A. Yavuz
    [J]. BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2018, 25 (05) : 699 - 715
  • [15] Decomposition of complete bipartite graphs into cycles and stars with four edges
    Ilayaraja, M.
    Muthusamy, A.
    [J]. AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 697 - 702
  • [16] A spectral condition for odd cycles in non-bipartite graphs
    Lin, Huiqiu
    Guo, Hangtian
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 631 : 83 - 93
  • [17] Packing directed cycles of specified odd length into digraphs and alternating cycles into bipartite graphs
    Chiba, Shuya
    Yoshida, Koshin
    [J]. DISCRETE MATHEMATICS, 2025, 348 (02)
  • [18] Efficient and privacy-preserving butterfly counting on encrypted bipartite graphs
    Pang, Xin
    Chen, Lanxiang
    [J]. JOURNAL OF INFORMATION SECURITY AND APPLICATIONS, 2025, 89
  • [19] CYCLABILITY IN BIPARTITE GRAPHS
    Amar, Denise
    Flandrin, Evelyne
    Gancarzewicz, Grzegorz
    [J]. OPUSCULA MATHEMATICA, 2009, 29 (04) : 345 - 364
  • [20] Bipartite graphs as polynomials and polynomials as bipartite graphs
    Grinblat, Andrey
    Lopatkin, Viktor
    [J]. JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2021, 20 (05)
12345