# Mitarbeiterseminar Logik in der Informatik

Freitag, 11. November 2005, 11:15 Uhr

RUD 25, Raum 4.410
## An efficient derandomisation for Color Coding

Dzifa Ametowobla

Humboldt-Universität zu Berlin

Color Coding is a method to design randomized FPT-algorithms for the
embedding of structures of bounded treewidth and some related
problems. The algorithms can be derandomised by the use of families
of perfect hash functions. Considering as an example the
parameterized path problem, p-Path, this talk presents the concept
of Color Coding. I will show an algorithm for p-Path due to Alon,
focusing on the choice of the hash functions and their
representation by random variables of restricted independence. The
talk will also include an outline of the construction of such random
variables.