Publications
Sort:
Open Access Issue
Counting Problems in Parameterized Complexity
Tsinghua Science and Technology 2014, 19(4): 410-420
Published: 30 July 2014
Abstract PDF (259.8 KB) Collect
Downloads:9

Parameterized complexity is a multivariate theory for the analysis of computational problems. It leads to practically efficient algorithms for many 𝐍𝐏-hard problems and also provides a much finer complexity classification for other intractable problems. Although the theory is mostly on decision problems, parameterized complexity naturally extends to counting problems as well. The purpose of this article is to survey a few aspects of parameterized counting complexity, with a particular emphasis on some general frameworks in which parameterized complexity proves to be indispensable.

Total 1