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 条
  • [1] Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result
    Dehghan, Ali
    Banihashemi, Amir H.
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2020, 68 (03) : 1378 - 1390
  • [2] On Finding Bipartite Graphs With a Small Number of Short Cycles and Large Girth
    Dehghan, Ali
    Banihashemi, Amir H.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (10) : 6024 - 6036
  • [3] On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix
    Dehghan, Ali
    Banihashemi, Amir H.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (10) : 6037 - 6047
  • [4] Rectangle Counting in Large Bipartite Graphs
    Wang, Jia
    Fu, Ada Wai-Chee
    Cheng, James
    2014 IEEE INTERNATIONAL CONGRESS ON BIG DATA (BIGDATA CONGRESS), 2014, : 17 - 24
  • [5] Families of Butterfly Counting Algorithms for Bipartite Graphs
    Acosta, Jay A.
    Low, Tze Meng
    Parikh, Devangi N.
    2022 IEEE 36TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW 2022), 2022, : 304 - 313
  • [6] On the Fundamental System of Cycles in the Bipartite Graphs of LDPC Code Ensembles
    Sason, Igal
    2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4, 2009, : 75 - 79
  • [7] The Complexity of Contracting Bipartite Graphs into Small Cycles
    Krithika, R.
    Sharma, Roohani
    Tale, Prafullkumar
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022), 2022, 13453 : 356 - 369
  • [8] Short rainbow cycles in graphs and matroids
    DeVos, Matt
    Drescher, Matthew
    Funk, Daryl
    Gonzalez Hermosillo de la Maza, Sebastian
    Guo, Krystal
    Huynh, Tony
    Mohar, Bojan
    Montejano, Amanda
    JOURNAL OF GRAPH THEORY, 2021, 96 (02) : 192 - 202
  • [9] Counting dominating sets in some subclasses of bipartite graphs
    Lin, Min-Sheng
    THEORETICAL COMPUTER SCIENCE, 2022, 923 : 337 - 347
  • [10] Null decomposition of bipartite graphs without cycles of length 0 modulo 4
    Jaume, Daniel A.
    Molina, Gonzalo
    Pastine, Adrian
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 614 (614) : 176 - 196
12345