Approximately counting paths and cycles in a graph

DOI10.1016/J.DAM.2016.09.002MaRDI QIDQ516844zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(12)

• Counting odd cycles in locally dense graphs
• Approximately counting approximately-shortest paths in directed acyclic graphs
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• 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)