An efficient approximation algorithm for counting n-cycles in a graph

DOI10.1016/J.AMC.2007.05.071MaRDI QIDQ2474910zbMATH OpenOpenAlexFDO

Authors Sheng Zhong

Publication date 6 March 2008

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2007.05.071

zbMATH Keywords

approximationerror boundgraph theorynumber of \(n\)-cyclespolynomial complexity

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1003265
• Approximately counting paths and cycles in a graph
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• Complexity of counting cycles using zeons

Cites work

• scientific article; zbMATH DE number 2094523 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• The number of n-cycles in a graph

Cited in

(7)

• A counting algorithm for a cyclic binary query
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• scientific article; zbMATH DE number 2077649 (Why is no real title available?)
• Finding even cycles faster via capped k-walks
• On the Complexity of Cycle Enumeration for Simple Graphs
• Complexity of counting cycles using zeons

This page was built for publication: An efficient approximation algorithm for counting \(n\)-cycles in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474910)