Abstract
We study the fixed parameter tractability of the counting version of a parameterization of the restrictive list H-coloring problem. The parameterization is defined by fixing the number of preimages of a subset C of the vertices in H through a weight assignment K on C. We show the fixed parameter tractability of counting the number of list (H, C, K)-colorings, for the case in which (H, C, K) is simple. We introduce the concept of compactor and a new algorithmic technique, compactor enumeration, that allow us to design fixed parameter algorithms for parameterized counting problems.
Original language | English (US) |
---|---|
Pages (from-to) | 919-937 |
Number of pages | 19 |
Journal | Journal of Computer and System Sciences |
Volume | 74 |
Issue number | 5 |
DOIs | |
State | Published - Aug 2008 |
Keywords
- Counting problems
- Parameterization
- Restrictive H-coloring
- Restrictive list H-coloring
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics