Forschung
Übersichtliches Zeichnen von Graphen
Graphen sind nicht nur ein häufiges Hilfsmittel beim Modellieren und Lösen von Problemen in der Informatik, sondern werden auch oft zur Visualisierung von Daten genutzt. Auch für Laien sind konkrete Zeichnungen von Graphen oft gut verständlich, da die Darstellung einer Verbindung oder eines Zusammenhangs durch Kanten intuitiv ist. Darüber hinaus lassen sich Methoden zum Zeichnen von Graphen auch oft für das Zeichnen realer Netzwerke, wie z.B. (U-)Bahnnetze, verwenden. Wir entwickeln und untersuchen Algorithmen für das übersichtliche Zeichnen von Graphen.
Algorithmen für Geographische Informationssysteme
Ein Geographisches Informationssystem (GIS) dient der Erfassung, Verwaltung, Analyse und Präsentation geographischer Information. In diesen Aufgabengebieten ergeben sich algorithmische Probleme, die oft geometrischer Natur sind. Beispielsweise müssen Gebäudeumrisse aus Rohdaten (z.B. aus 3D Punktwolken, die mittels Laserscanning gewonnen wurden) generiert werden. Grundsätzlich werden Geodaten benötigt, deren Abstraktions- bzw. Detailgrad zur jeweiligen Anwendung (z.B. zur Städteplanung oder Klimamodellierung) passt. Daher sind Algorithmen zur automatischen Generalisierung erforderlich, welche einen Geodatensatz an einen höheren Abstraktions- bzw. niedrigeren Detailgrad anpassen können. Insbesondere wird die Generalisierung bei der kartographischen Visualisierung eingesetzt, um übersichtliche Landkarten zu erzeugen, wobei sie mit einer Reduktion des Kartenmaßstabs einhergeht.
Kompetitive Standortprobleme
Wir untersuchen eine Klasse von Standortproblemen, bei denen zwei konkurrierende Anbieter ihre Versorger sequenziell platzieren, und die Kunden sich zwischen den Konkurrenten entscheiden können. Wir nehmen an, dass beide Konkurrenten nicht-kooperativ agieren und auf die Maximierung ihres eigenen Vorteils abzielen. Wir untersuchen die Komplexität und Approximierbarkeit solcher Probleme auf Graphen, insbesondere auf einfachen Graphklassen wie Bäumen und Pfaden. Ferner entwickeln wir schnelle Algorithmen für kompetitive Einzelstandortprobleme, bei denen jeder Anbieter genau einen Versorger errichtet.
Komplexität und Automaten
Wir untersuchen Eigenschaften vollständiger Mengen von Komplexitätsklassen, z.B. die Redundanz NP-vollständiger Mengen. Man vermutet, dass alle NP-vollständigen Mengen hochgradig redundant sind, kann dies aber nicht allgemein zeigen. Daher sucht man nach schwächeren Redundanzaussagen, die sich für alle NP-vollständigen Mengen nachweisen lassen.
Optimierung für den öffentlichen Verkehr
Hochfrequent, von Tür zu Tür, mit kurzen Reisezeit und robust gegen Störungen - so wünschen wir uns den öffentlichen Verkehr, damit er eine echte Alternative zum Auto darstellt. Neben diesen Qualitätsansprüchen wollen Verkehrsbetriebe natürlich auch Kosten und zunehmend auch Emissionen klein halten.
Traditionell wird das Erstellen eines Verkehrsangebots in die Schritte Infrastrukturplanung, Linienplanung, Fahrplanung, Materialplanung, Personalplanung unterteilt. Diese Planungsprobleme werden, teilweise basiert auf sehr vereinfachenden Annahmen, oft mit Hilfe von Netzwerken modelliert und mit Methoden der ganzzahligen linearen Optimierung gelöst.
Spannende Herausforderungen ergeben sich dort, wo vereinfachende Annahmen mit realistischeren ersetzt werden, zum Beispiel im Bereich Nachfragemodellierung oder Datenverfügbarkeit. Wir beschäftigen uns mit der Modellierung und Lösung solcher Optimierungsprobleme.
