On Counting Parameterized Matching and Packing
From MaRDI portal
Publication:4632178
DOI10.1007/978-3-319-39817-4_13zbMATH Open1475.68248OpenAlexW2493989425MaRDI QIDQ4632178FDOQ4632178
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
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
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Improved algorithms for path, matching, and packing problems
- Limits and Applications of Group Algebras for Parameterized Problems
- Counting Paths and Packings in Halves
- Monte-Carlo approximation algorithms for enumeration problems
- The Parameterized Complexity of Counting Problems
- The parameterised complexity of counting connected subgraphs and graph motifs
- Title not available (Why is that?)
- Parameterized counting problems
- Parameterized and Exact Computation
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Counting matchings of size \(k\) is \#W[1]-hard
- On counting 3-D matchings of size \(k\)
- Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
Cited In (9)
- 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
- Title not available (Why is that?)
- 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)
- A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
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)