Finding and counting given length cycles

被引：328

作者：

Alon, N

Yuster, R

Zwick, U

机构：

[1] School of Mathematical Sciences, Raymond Beverly Sackler Fac. E., Tel Aviv University

来源：

ALGORITHMICA | 1997年 / 17卷 / 03期

关键词：

graph algorithms; cycles;

D O I：

10.1007/BF02523189

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs, Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results.

引用

页码：209 / 223

页数：15

共 16 条

[1] COLOR-CODING [J].

ALON, N ;

YUSTER, R ;

ZWICK, U .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04) :844-856

[2]

ALON N, 1994, LNCS, V855, P354

[3] ON GENERALIZED GRAPHS [J].

BOLLOBAS, B .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1965, 16 (3-4) :447-&

[4]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[5]

Bondy J. A., 1974, Journal of Combinatorial Theory, Series B, V16, P97, DOI 10.1016/0095-8956(74)90052-5

[6] ARBORICITY AND SUBGRAPH LISTING ALGORITHMS [J].

CHIBA, N ;

NISHIZEKI, T .

SIAM JOURNAL ON COMPUTING, 1985, 14 (01) :210-223

[7]

EPPSTEIN D, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P632

[8] FINDING A MINIMUM CIRCUIT IN A GRAPH [J].

ITAI, A ;

RODEH, M .

SIAM JOURNAL ON COMPUTING, 1978, 7 (04) :413-423

[9]

KLOKS T, 1995, P 21 INT WORKSH GRAP, V1017, P14

[10] SMALLEST-LAST ORDERING AND CLUSTERING AND GRAPH-COLORING ALGORITHMS [J].

MATULA, DW ;

BECK, LL .

JOURNAL OF THE ACM, 1983, 30 (03) :417-427

← 1 2 →