Komplexität und Approximierbarkeit kompetitiver 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. » mehr

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. » mehr

Ü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. » mehr