Efficient algorithms for counting parameterized list H-colorings

Josep Díaz, Maria Serna, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)919-937
Number of pages19
JournalJournal of Computer and System Sciences
Volume74
Issue number5
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Efficient algorithms for counting parameterized list H-colorings'. Together they form a unique fingerprint.

Cite this