Parameterized counting problems
From MaRDI portal
Publication:2576944
DOI10.1016/j.apal.2005.06.010zbMath1133.68027OpenAlexW1983207144MaRDI QIDQ2576944
Publication date: 29 December 2005
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2005.06.010
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (11)
Compactors for parameterized counting problems ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ A Basic Parameterized Complexity Primer ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ On Counting Parameterized Matching and Packing ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ The parameterized complexity of \(k\)-edge induced subgraphs
Cites Work
- On the efficiency of polynomial time approximation schemes
- The complexity of computing the permanent
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Perfect Code is \(W[1\)-complete]
- The Turing way to parameterized complexity
- Vertex Cover: Further Observations and Further Improvements
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Parameterized counting problems
