TY - CHAP
T1 - Fixed parameter algorithms for counting and deciding bounded restrictive list H-colorings
AU - Díaz, Josep
AU - Serna, Maria
AU - Thilikos, Dimitrios M.
PY - 2004
Y1 - 2004
N2 - We study the fixed parameter tractability of the parameterized counting and decision version of the restrictive H-coloring problem. These problems are defined by fixing the number of preimages of a subset C of the vertices in H through a partial weight assignment (H,C,K). We consider two families of partial weight assignment the simple and the plain. For simple partial weight assignments we show an FPT algorithm for counting list (H, C, K)-colorings and faster algorithms for its decision version. For the more general class of plain partial weight assignment we give an FPT algorithm for the (H, C, K)-coloring decision problem. We introduce the concept of compactor and an algorithmic technique, compactor enumeration, that allow us to design the FPT algorithms for the counting version (and probably export the technique to other problems).
AB - We study the fixed parameter tractability of the parameterized counting and decision version of the restrictive H-coloring problem. These problems are defined by fixing the number of preimages of a subset C of the vertices in H through a partial weight assignment (H,C,K). We consider two families of partial weight assignment the simple and the plain. For simple partial weight assignments we show an FPT algorithm for counting list (H, C, K)-colorings and faster algorithms for its decision version. For the more general class of plain partial weight assignment we give an FPT algorithm for the (H, C, K)-coloring decision problem. We introduce the concept of compactor and an algorithmic technique, compactor enumeration, that allow us to design the FPT algorithms for the counting version (and probably export the technique to other problems).
UR - http://www.scopus.com/inward/record.url?scp=35048825285&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048825285&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30140-0_26
DO - 10.1007/978-3-540-30140-0_26
M3 - Chapter
AN - SCOPUS:35048825285
SN - 3540230254
SN - 9783540230250
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 275
EP - 286
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Albers, Susanne
A2 - Radzik, Tomasz
PB - Springer Verlag
ER -