Loading…
Aspects of Preprocessing Applied to Combinatorial Graph Problems
Weller, Mathias
Diese Arbeit beschäftigt sich mit diversen Aspekten effizienter (also in Polynomzeit ausführbarer) Vorverarbeitung für NP-schwere Probleme im Kontext der Parameterisierten Komplexitätstheorie. Im Einzelnen geht es um Nichtstandardparameter, Linearzeitkernelisierung, Vorverarbeitung ohne Problemkern und parallelisierbare Turingkerne, welche alle von praktischer Relevanz sind. Besonders hervorzuheben ist das letztgenannte Thema, zu welchem erste theoretische Pionierarbeit geleistet wird.
This work considers multiple aspects of efficient (that is, polynomial-time executable) preprocessing for NP-hard problems in the context of parameterized complexity theory. Special emphasis is put on the following topics: Non-standard parameterization, linear-time kernelization, preprocessing beyond kernelization, and parallelizable Turing kernelization. All these topics are practically relevant and, pioneering work on parallelizable Turing kernelizations, the final topic is of special theoretical interest.
Published by Universitätsverlag der TU Berlin, ISBN 978-3-7983-2509-8
- Die Printversion ist im Universitätsverlag der TU Berlin unter ISBN 978-3-7983-2508-1 erschienen und im Buchhandel lieferbar. .
