Parameterized counting problems

Annals of Pure and Applied Logic 138 (1):147-182 (2006)
  Copy   BIBTEX

Abstract

Parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to new insight into counting problems. The goal of this article is to introduce a formal framework in which one may consider parameterized counting problems

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2005.06.010

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,757

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The parameterized complexity of maximality and minimality problems.Yijia Chen & Jörg Flum - 2008 - Annals of Pure and Applied Logic 151 (1):22-61.
Advice classes of parameterized tractability.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - Annals of Pure and Applied Logic 84 (1):119-138.
Sparse parameterized problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.
Computation models for parameterized complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Parameterized Complexity of Propositional Inclusion and Independence Logic.Yasir Mahmood & Jonni Virtema - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 274-291.
On the parameterized complexity of short computation and factorization.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - Archive for Mathematical Logic 36 (4-5):321-337.
Corrigendum to “Advice classes of parameterized tractability” [Ann. Pure Appl. Logic 84 (1) (1997) 119–138].Liming Cai, Jainer Chen, Rod Downey & Mike Fellows - 2018 - Annals of Pure and Applied Logic 169 (5):463-465.
Complexity of the two-variable fragment with counting quantifiers.Ian Pratt-Hartmann - 2005 - Journal of Logic, Language and Information 14 (3):369-395.
Parameterized Complexity.R. G. Downey & M. R. Fellows - 2002 - Bulletin of Symbolic Logic 8 (4):528-529.

Analytics

Added to PP
2013-12-31

Downloads
38 (#598,068)

6 months
15 (#212,687)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references