|
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ätstheorieModified parameterized complexity theory
Kurzfassung in DeutschWird 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 EnglischWhen 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.
Ein kostenloser Dienst Ihrer Universitätsbibliothek Freiburg. |
