Servicenavigation

Project Details

Back

Projekt Print View

Effizientere Algorithmen für polynomialzeitlösbare Graphprobleme

Antragsteller Dr. André Nichterlein, since 5/2022
Subject Area Theoretische Informatik
Term from 2017 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 327762855
 
Final Report Year 2023

Final Report Abstract

Im Rahmen des FPTinP-Projektes entwickelten wir ein vertieftes Verständnis für die Parametrisierte Komplexität verschiedener polynomialzeitlösbarer Graphprobleme. Für etliche im Antrag beschriebenen Probleme publizierten wir parametrisierte Algorithmen und parametrisierte untere Laufzeitschranken. Nachfolgend gehen wir kurz auf vier Hauptergebnisse ein. • Wir entwickelten eine allgemeine Methoden zur Erlangung von parametrisierten unteren Laufzeitschranken [P18]. Mit diesen belegten wir, dass mehrere, zum Teil triviale, parametrisierte Algorithmen unter üblichen Annahmen nicht beschleunigt werden können. • Für die Berechnung von Matchings größtmöglicher Kardinalität bzw. Gewichts erwies sich Vorverarbeitung durch Datenreduktionsregeln als sehr vorteilhaft. Die vorherige Anwendung unserer Problemkerne beschleunigt aktuelle Algorithmen signifikant – durchschnittlich um mehr als Faktor 4. • Für verschiedene Probleme, wie z. B. der Berechnung der Betweeness Centrality oder von größtmöglichen Matchings konnten wir sogenannte „adaptive“ Algorithmen entwickeln, d. h., Algorithmen die bei großen Parameterwerten nicht langsamer als die aktuell schnellsten sind, aber bei kleinen Parameterwerten eine bessere Worst-Case-Komplexität haben. • Obwohl der Durchmesser eines Graphen polynomialzeitberechenbar ist, ergaben sich für die meisten betrachteten Parametrisierungen untere Laufzeitschranken mit exponentiellen Abhängigkeiten im Parameter.

Publications

 
 

Additional Information

© 2026 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung