On Counting Parameterized Matching and Packing

DOI10.1007/978-3-319-39817-4_13MaRDI QIDQ4632178zbMATH OpenOpenAlexFDO

Authors Yunlong Liu, Jianxin Wang

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_13

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
• On counting 3-D matchings of size \(k\)
• scientific article; zbMATH DE number 1979521
• Counting matchings of size \(k\) is \#W[1]-hard

Cites work

• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• Counting Paths and Packings in Halves
• Counting matchings of size \(k\) is \#W[1]-hard
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Improved algorithms for path, matching, and packing problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Monte-Carlo approximation algorithms for enumeration problems
• On counting 3-D matchings of size \(k\)
• Parameterized and Exact Computation
• Parameterized counting problems
• The Parameterized Complexity of Counting Problems
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The parameterised complexity of counting connected subgraphs and graph motifs

Cited in

(9)

• A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
• Parameterized algorithms for weighted matching and packing problems
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Algorithms and Data Structures
• scientific article; zbMATH DE number 434914 (Why is no real title available?)
• On counting 3-D matchings of size \(k\)
• Counting matchings of size \(k\) is \#W[1]-hard
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)

This page was built for publication: On Counting Parameterized Matching and Packing

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