FPTAS for counting weighted edge covers

DOI10.1007/978-3-662-44777-2_54MaRDI QIDQ2921451zbMATH OpenOpenAlexFDO

Authors Jing-Cheng Liu, Pinyan Lu, Chihao Zhang

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_54

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• A simple FPTAS for counting edge covers
• scientific article; zbMATH DE number 2119674
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• scientific article; zbMATH DE number 2119675

Cited in

(9)

• The complexity of Bayesian networks specified by propositional and relational languages
• Zeros and approximations of holant polynomials on the complex plane
• Some applications of Wagner's weighted subgraph counting polynomial
• On the connection between interval size functions and path counting
• On the Complexity of Holant Problems
• A simple FPTAS for counting edge covers
• Absence of zeros implies strong spatial mixing
• Spectral independence via stability and applications to Holant-type problems
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting

This page was built for publication: FPTAS for counting weighted edge covers

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