Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Journal Article Printable view
Finding and counting given length cycles

Finding and counting given length cycles

JournalAlgorithmica
PublisherSpringer New York
ISSN0178-4617 (Print) 1432-0541 (Online)
IssueVolume 17, Number 3 / March, 1997
DOI10.1007/BF02523189
Pages209-223
Subject CollectionComputer Science
SpringerLink DateSaturday, March 01, 1997
Add to marked items

Finding and counting given length cycles

N. Alon1 Contact Information, R. Yuster1 Contact Information and U. Zwick1 Contact Information

(1)  School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, 69978 Tel Aviv, Israel

Received: 18 October 1994  Revised: 5 May 1995  

Communicated by N. Megiddo.
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.

Key Words  Graph algorithms - Cycles

This work was supported in part by The Basic Research Foundation administrated by The Israel Academy of Sciences and Humanities.

Contact Information N. Alon
Email: noga@math.tau.ac.il

Contact Information R. Yuster
Email: raphy@math.tau.ac.il

Contact Information U. Zwick
Email: zwick@math.tau.ac.il
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this article
Export this article as RIS | Text
 
Referenced by
17 newer articles

  1. Kortsarz, Guy (2010) Approximating Maximum Subgraphs without Short Cycles. SIAM Journal on Discrete Mathematics 24(1)
    [CrossRef]
  2. Hu, Jialu (2009) Evaluation of subgraph searching algorithms detecting network motif in biological networks. Frontiers of Computer Science in China 3(3)
    [CrossRef]
  3. Czumaj, Artur (2009) Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication. SIAM Journal on Computing 39(2)
    [CrossRef]
  4. Feder, Tomás (2002) Approximating the Longest Cycle Problem in Sparse Graphs. SIAM Journal on Computing 31(5)
    [CrossRef]
  5. Yang, Bo (2009) Method for quickly inferring the mechanisms of large-scale complex networks based on the census of subgraph concentrations. Journal of Systems Science and Complexity 22(2)
    [CrossRef]
  6. Ma'ayan, A. (2008) Ordered cyclic motifs contribute to dynamic stability in biological and engineered networks. Proceedings of the National Academy of Sciences 105(49)
    [CrossRef]
  7. Fricker, Mark D. (2008) The Interplay between Structure and Function in Fungal Networks. Topologica 1(1)
    [CrossRef]
  8. Alon, Noga (2008) Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Algorithmica
    [CrossRef]
  9. Naor, Assaf (2008) Parity check matrices and product representations of squares. COMBINATORICA 28(2)
    [CrossRef]
  10. Chan, Timothy M. (2006) Dynamic Subgraph Connectivity with Geometric Applications. SIAM Journal on Computing 36(3)
    [CrossRef]
First | Next | Last
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.118 • Server: mpweb17
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)