An algorithm for counting short cycles in bipartite graphs

被引：58

作者：

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

共 22 条

[1] Finding and counting given length cycles [J].

Alon, N ;

Yuster, R ;

Zwick, U .

ALGORITHMICA, 1997, 17 (03) :209-223

[2]

[Anonymous], P 20 BIENN S COMM KI

[3] Design of parallel concatenated convolutional codes [J].

Benedetto, S ;

Montorsi, G .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1996, 44 (05) :591-600

[4] An updated set of Basic Linear Algebra Subprograms (BLAS) [J].

Blackford, LS ;

Demmel, J ;

Dongarra, J ;

Duff, I ;

Hammarling, S ;

Henry, G ;

Heroux, M ;

Kaufman, L ;

Lumsdaine, A ;

Petitet, A ;

Pozo, R ;

Remington, K ;

Whaley, RC .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2002, 28 (02) :135-151

[5]

Chugg K. M., 2001, ITERATIVE DETECTION

[6]

Diestel R., 2000, GRAPH THEORY

[7]

Flum J, 2002, ANN IEEE SYMP FOUND, P538, DOI 10.1109/SFCS.2002.1181978

[8] LOW-DENSITY PARITY-CHECK CODES [J].

GALLAGER, RG .

IRE TRANSACTIONS ON INFORMATION THEORY, 1962, 8 (01) :21-&

[9]

HALFORD TR, 2004, 2004 COMM THEOR WORK

[10] Regular and irregular progressive edge-growth tanner graphs [J].

Hu, XY ;

Eleftheriou, E ;

Arnold, DM .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (01) :386-398

← 1 2 3 →