Approximately counting paths and cycles in a graph
type: Item
instance of: scholarly article
title: Approximately counting paths and cycles in a graph
zbMATH Open document ID: 1358.05140
author: Masaki Yamamoto
published in: Discrete Applied Mathematics
publication date: 2017-03-15T00:00:00Z
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6695046
zbMATH Keywords: approximate counting
zbMATH Keywords: \(\#\mathrm{P}\)-hard
zbMATH Keywords: FPRAS
zbMATH Keywords: inapproximability
MaRDI profile type: Publication
full work available at URL: j.dam.2016.09.002
OpenAlex ID: W2522462178
cites work: On Counting Independent Sets in Sparse Graphs
cites work: The relative complexity of approximate counting problems
cites work: An approximation trichotomy for Boolean \#CSP
cites work: On Markov Chains for Independent Sets
cites work: Counting trees in a graph is \(\# \text{P}\)-complete
cites work: Approximating the Permanent
cites work: Polynomial-Time Approximation Algorithms for the Ising Model
cites work: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
cites work: Monte-Carlo algorithms for the planar multiterminal network reliability problem
cites work: Q4527036
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Counting independent sets up to the tree threshold
cites work: On Unapproximable Versions of $NP$-Complete Problems
DOI: 10.1016/J.DAM.2016.09.002
description: scientific article; zbMATH DE number 6695046