Approximately counting paths and cycles in a graph

DOI10.1016/J.DAM.2016.09.002zbMATH Open1358.05140OpenAlexW2522462178MaRDI QIDQ516844FDOQ516844

Authors: Masaki Yamamoto 

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.002

Recommendations

• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• The Parameterized Complexity of Counting Problems
• scientific article; zbMATH DE number 1003265
• scientific article; zbMATH DE number 1670534
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs

zbMATH Keywords

approximate countinginapproximabilityFPRAS\(\#\mathrm{P}\)-hard

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• The complexity of computing the permanent
• The relative complexity of approximate counting problems
• The Complexity of Enumeration and Reliability Problems
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Unapproximable Versions of $NP$-Complete Problems
• An approximation trichotomy for Boolean \#CSP
• Approximating the Permanent
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• On Counting Independent Sets in Sparse Graphs
• Title not available (Why is that?)
• On Markov Chains for Independent Sets
• Counting trees in a graph is \(\# \text{P}\)-complete

Cited In (12)

• Counting odd cycles in locally dense graphs
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Title not available (Why is that?)
• Increasing paths in countable graphs
• Counting substrate cycles in topologically restricted metabolic networks
• Tools for counting odd cycles in graphs
• Subgraph summability number of paths and cycles
• Counting paths in graphs
• Counting paths, cycles, and blow‐ups in planar graphs
• Complexity of counting cycles using zeons
• An efficient approximation algorithm for counting \(n\)-cycles in a graph
• On computing the path number of a graph

This page was built for publication: Approximately counting paths and cycles in a graph

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