Exploiting New Types of Structure for Fixed Parameter Tractability

01.07.2014 - 28.02.2018
Forschungsförderungsprojekt

 Viele wichtige algorithmische Probleme sind im allgemeinen nicht effizient lösbar, aber oft ist es möglich, gewisse strukturelle Eigenschaften von Problemeingaben auszunutzen um dennoch eine effiziente Lösung zu erreichen. Bisherige Forschung hat verschieden strukturellen Eigenschaften identifiziert, welche die Lösung des Problems in Polynomialzeit ermöglichen. Eine zentrale Frage dieses Forschungsprojektes ist es, wie diese effizienten Lösungsmethoden auch für solche Problemeingaben nutzbar gemacht werden können, die diese strukturellen Eigenschaften nicht zur Gänze erfüllen. Im Speziellen soll die Lösbarkeit von Problemeingaben untersucht werden, bei denen gewisse strukturelle Eigenschaften durch eine kleine Anzahl von elementaren Änderungen erreicht werden können. Die Anzahl dieser Änderungen dient als Parameter für parametrisierte Algorithmen. Das Gesamtziel ist es, eine rigorose Methodik zu entwickeln, die für viele wichtige algorithmische Problem anwendbar ist, und die es ermöglicht, strukturelle Eigenschaften von Problemeingaben auszunutzen, die für bekannte Methoden nicht nutzbar sind. Neben effizienten Algorithmen sollen auch euch neue Methoden für untere Schranken für Laufzeitanalysen entwickelt werden.

Personen

Projektleiter_in

Institut

Förderungsmittel

  • FWF - Österr. Wissenschaftsfonds (National)

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
modulator to a graph classmodulator to a graph class
Parameterized ComplexityParameterized Complexity
backdoorsbackdoors
kernelizationkernelization