Efficient algorithms for counting parameterized list H-colorings |
| |
Authors: | Josep Díaz Maria Serna Dimitrios M Thilikos |
| |
Affiliation: | aALBCOM Research Group, Dept. Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Campus Nord, Edifici Ω, Jordi Girona Salgado 1-3, 08034 Barcelona, Spain;bDepartment of Mathematics, National and Kapodistrian University of Athens, Panepistimioupolis, GR157 84 Athens, Greece |
| |
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. |
| |
Keywords: | Restrictive H-coloring Restrictive list H-coloring Parameterization Counting problems |
本文献已被 ScienceDirect 等数据库收录! |
|