Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Advanced kernelization algorithms
verfasst von : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized Algorithms
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
The systematic study of the kernelization framework, whose foretaste we had in Chapter
2
, revealed an intrinsic mathematical richness of this notion. In particular, many classic techniques turn out to be very useful in this context; examples include tools of combinatorial optimization, linear algebra, probabilistic arguments, or results of the graph minors theory. In this chapter, we provide an overview of some of the most interesting examples of more advanced kernelization algorithms. In particular, we provide a quadratic kernel for the
F
eedback
V
ertex
S
et
problem. We also discuss the topics of
above guarantee parameterizations
in the context of kernelization, of kernelization on planar graphs, and of so-called
Turing kernelization.