Bitte wählen Sie ihr Lieferland und ihre Kundengruppe
In dieser Arbeit werden verschiedene Aspekte effizienter (in polynomieller Zeit ausführbarer) Vorverarbeitung für NP-schwere Probleme untersucht. Besonderer Schwerpunkt liegt dabei auf praktisch relevanten Eigenschaften der Vorverarbeitung. Zur Untersuchung dieser Eigenschaften dient die parametrisierte Komplexitätstheorie, da sie die nötigen Werkzeuge zur Analyse von Vorverarbeitungsalgorithmen bereitstellt. In der parametrisierten Komplexitätstheorie wird die Komplexität eines Problems nicht nur in der Größe der Eingabe, sondern auch im Parameter", einer natürlichen Zahl, die eine Eigenschaft der Eingabe repräsentiert, gemessen. Dadurch lasst sich die Güte einer Vorverarbeitung, die eine zur Eingabe äquivalente, jedoch kleinere Instanz produziert beschreiben, indem die Ausgabe des Vorverarbeitungsalgorithmus durch eine Funktion im Parameter nach oben beschränkt wird. Hierbei gilt üblicherweise das Motto je kleiner desto besser". Ein solcher Algorithmus wird auch als Kernelisierung bezeichnet, und die Ausgabe einer Kernelisierung ist ein Problemkern. Die folgenden Aspekte effizienter Vorverarbeitung werden in der Arbeit diskutiert: Nichtstandardparameter; effiziente Vorverarbeitung; Vorverarbeitung über Kernelisierung hinaus; zwischen Turing- und klassischer Kernelisierung.
This work considers multiple aspects of efficient (that is, polynomial-time executable) preprocessing for NP-hard problems with emphasis on practically relevant properties. A theoretical framework for the development and analysis of preprocessing algorithms is supplied by parameterized complexity theory. Herein, the complexity of a problem is measured not only in the size of the input, but also in some other aspect measurable by a natural number. This aspect is called the "parameter". Then, a kernelization is a polynomial-time algorithm that, given an instance, computes an equivalent, smaller instance (the problem kernel) whose size can be bounded by a function of the parameter. This allows measuring the performance of a preprocessing (that is, the size of the output instance). Here, the usual motto is "the smaller the output instance, the better the preprocessing algorithm".