Aspects of Preprocessing
Applied to Combinatorial Graph Problems
Umfang: 195 Seiten
Erscheinungsjahr: 2013
ISBN 978-3-7983-2508-1Erscheinungsjahr: 2013
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.