Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
From MaRDI portal
Publication:2636502
DOI10.1016/j.tcs.2017.09.022zbMath1393.68076OpenAlexW2758053690MaRDI QIDQ2636502
Jianxin Wang, Shaokai Wang, Yunlong Liu
Publication date: 5 June 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.022
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- Improved deterministic algorithms for weighted matching and packing problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Parameterized algorithms for weighted matching and packing problems
- An improved kernelization for \(P_{2}\)-packing
- On counting 3-D matchings of size \(k\)
- Using nondeterminism to design efficient deterministic algorithms
- The parameterised complexity of counting connected subgraphs and graph motifs
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem
- Parametrized complexity theory.
- Parameterized counting problems
- Edge-disjoint packing of stars and cycles
- Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
- Iterative Expansion and Color Coding
- Improved Parameterized Algorithms for Weighted 3-Set Packing
- Limits and Applications of Group Algebras for Parameterized Problems
- Counting Paths and Packings in Halves
- Monte-Carlo approximation algorithms for enumeration problems
- Color-coding
- The Parameterized Complexity of Counting Problems
- Parameterized and Exact Computation
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
