Aspects of Preprocessing

Applied to Combinatorial Graph Problems

Umfang: 195 Seiten
Erscheinungsjahr: 2013
ISBN 978-3-7983-2508-1
12,00 

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.