Stetige Standortplanung auf Graphen

• Antragsteller: Professor Dr. Peter Rossmanith, seit 6/2022
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 447534137

Wir betrachten stetige Standortplanungsprobleme auf Graphen, in denen alle Kanten Einheitslänge haben und in denen sowohl die Knoten als auch die inneren Punkte der Kanten potentielle Standorte sind. Das Ziel ist es, entweder den gesamten Graphen mit möglichst wenigen Standorten mit Ueberdeckungsradius \delta zu überdecken (Überdeckungsvariante), oder möglichst viele Standorte zu platzieren, die paarweise einen Abstand von mindestens \delta zu einander haben.Die Ziele im Projekt sind die Analyse der Approximierbarkeit und der Nicht-Approximierbarkeit von derartigen Standortplanungsproblemen, das Studium von ihrem Verhalten auf speziell strukturierten Graphklassen, und die Untersuchung ihrer Komplexität.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr.-Ing. Gerhard Woeginger, bis 6/2022