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 -