Kernelization: Theory of Parameterized Preprocessing

ISBN-13: 9781107057760 / Angielski / Twarda / 2019 / 528 str.

Fedor V. Fomin; Daniel Lokshtanov; Saket Saurabh

Opis

A complete introduction to recent advances in preprocessing analysis, or kernelization, with extensive examples using a single data set.

Recenzje

'The book manages to present an incredible number of techniques, methods, and examples in its 528 pages. Each chapter ends with a bibliographic notes section, which often provides some small historical context for the material covered. It also points to more current results and papers although it does so very briefly. Together, this makes the textbook a valuable resource book to researchers.' Tim Jackman and Steve Homer, SIGACT News

Spis treści

1. What is a kernel?; Part I. Upper Bounds: 2. Warm up; 3. Inductive priorities; 4. Crown decomposition; 5. Expansion lemma; 6. Linear programming; 7. Hypertrees; 8. Sunflower lemma; 9. Modules; 10. Matroids; 11. Representative families; 12. Greedy packing; 13. Euler's formula; Part II. Meta Theorems: 14. Introduction to treewidth; 15. Bidimensionality and protrusions; 16. Surgery on graphs; Part III. Lower Bounds: 17. Framework; 18. Instance selectors; 19. Polynomial parameter transformation; 20. Polynomial lower bounds; 21. Extending distillation; Part IV. Beyond Kernelization: 22. Turing kernelization; 23. Lossy kernelization.