• Startseite
• Recherche
• Veröffentlichen
• Hilfe

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-42765
URL: http://www.freidok.uni-freiburg.de/volltexte/4276/

Weyer, Mark

Modifizierte parametrische Komplexitätstheorie

Modified parameterized complexity theory

Kurzfassung in Deutsch

Wird die erlaubte Parameterabhängigkeit einer FPT-Laufzeit eingeschränkt, so muß auch der Reduktionsbegriff angepasst werden. So entstehen modifizierte parametrische Komplexitätstheorien, das sind Theorien der Grade parametrisierter Probleme unter den modifizierten Reduktionen.

Die Arbeit untersucht vor allem den allgemeinen Rahmen modifizierter Theorien, sowohl abstrakt als auch im Hinblick auf konkrete Klassen der unmodifizierten parametrischen Komplexitätstheorie.

Die entwickelten Begriffe ermöglichen auch, die für FPT-Algorithmen notwendige Parameterabhängigkeit von Problemen in FPT zu untersuchen. Dies geschieht am Beispiel des parametrisierten Model-Checking Problems für Wörter und Strukturen beschränkter Baumweite.

Kurzfassung in Englisch

When the permitted parameter dependence of an FPT running time is restricted, the notion of reduction has to be adjusted. This leads to modified parameterized complexity theories, that is theories of the degrees of parameterized problems under the modified reductions.

The paper mainly considers the general frame of modified theories. This is done both in an abstract way and with concrete classes of unmodified parameterized complexity theory in mind.

For problems in FPT, the developed notions also enable one to investigate the parameter dependence required for FPT algorithms. This is done for the parameterized model checking problem on words or structures of bounded tree-width.