Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

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.

Zurück zur Vortragsübersicht 

Last modified: Tue Nov 15 11:37:06 CET 2005
André Hernich