A Simple FPTAS for Counting Edge Covers

DOI10.1137/1.9781611973402.25zbMath1422.68303arXiv1309.6115OpenAlexW3105627268MaRDI QIDQ5383984

Pinyan Lu, Jing-Cheng Liu, Cheng-yu Lin

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.6115

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (10)

Zero-freeness and approximation of real Boolean Holant problems ⋮ Absence of zeros implies strong spatial mixing ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ On the Complexity of Holant Problems ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ Some applications of Wagner's weighted subgraph counting polynomial ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

This page was built for publication: A Simple FPTAS for Counting Edge Covers