Finding and Counting Given Length Cycles

N. Alon; R. Yuster; U. Zwick

doi:10.1007/BF02523189

Finding and Counting Given Length Cycles

N. Alon, R. Yuster, U. Zwick

Research output: Contribution to journal › Article › peer-review

453 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	209-223
Number of pages	15
Journal	Algorithmica (New York)
Volume	17
Issue number	3
DOIs	https://doi.org/10.1007/BF02523189
State	Published - Mar 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Keywords

Cycles
Graph algorithms

Access to Document

10.1007/BF02523189

Cite this

@article{01a8eeca602348b0b1673ebde1bd20f4,

title = "Finding and Counting Given Length Cycles",

abstract = "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.",

keywords = "Cycles, Graph algorithms",

author = "N. Alon and R. Yuster and U. Zwick",

year = "1997",

month = mar,

doi = "10.1007/BF02523189",

language = "English (US)",

volume = "17",

pages = "209--223",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Finding and Counting Given Length Cycles

AU - Alon, N.

AU - Yuster, R.

AU - Zwick, U.

PY - 1997/3

Y1 - 1997/3

N2 - 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.

AB - 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.

KW - Cycles

KW - Graph algorithms

UR - http://www.scopus.com/inward/record.url?scp=0000445027&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000445027&partnerID=8YFLogxK

U2 - 10.1007/BF02523189

DO - 10.1007/BF02523189

M3 - Article

AN - SCOPUS:0000445027

SN - 0178-4617

VL - 17

SP - 209

EP - 223

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 3

ER -

Finding and Counting Given Length Cycles

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this