Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Randomized Techniques for Parameterized Algorithms
verfasst von : Dániel Marx
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Since the introduction of the Color Coding technique in 1994 by Alon, Yuster, and Zwick, randomization has been part of the toolkit for proving fixed-parameter tractability results. It seems that randomization is very well suited to parameterized algorithms: if the task is to find a solution of size
k
and only those random choices need to be correct that are directly related to the solution, then typically we can bound the error probability by a function of
k
. The talk will overview through various concrete examples how randomization appears in fixed-parameter tractability results. We argue that in many cases randomization appears in form of a reduction: it allows us to reduce the problem we are trying to solve to an easier and more structured problem.