Aspects of Preprocessing
Applied to Combinatorial Graph Problems
Buch in deiner Nähe kaufen
Beschreibung
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.
Autor*in
Mathias Weller
Themen in »Aspects of Preprocessing«
Effiziente Vorverarbeitung Fixed-Parameter Tractability Graphen Kernelisation Kernelization NP-hard Problems preprocessin Networks Nichtstandardparameter Parameterisierte Komplexität Theoretische Informatik Truthtable Kernel Turing Kernel