Folgeprojekt: Algorithmische Methoden für Kreuzungszahlen und andere Nichtplanaritätsmaße
Projektstatus: abgeschlossen
Drittmittelprojekt uri icon

Projektleitung

Beschreibung

  • Die Kreuzungszahl eines Graphen ist die kleinste Anzahl an paarweisen Kantenkreuzungen die notwendig ist, um den Graphen in der Ebene zu zeichnen. Das Problem, die Kreuzungszahl zu bestimmen, ist ein klassisches Problem der topologischen Graphentheorie und der wohl bekannteste Stellvertreter einer ganzen Reihe von Maßen der Nichtplanarität. Insbesondere zu Beginn seiner 70-jährigen Geschichte wurde das Kreuzungszahlproblem vor allem aus graphentheoretischer Sicht betrachtet. Nach anfänglich eher langsamen Fortschritten von Seiten der Algorithmik, brachten insbesondere die letzten 10-20 Jahre zahlreiche algorithmische Entwicklungen, um das NP-vollständige Kreuzungszahlproblem besser zu verstehen. Dennoch sind noch immer diverse grundlegende Fragen, z.B. nach der Approximierbarkeit des Problems, unbeantwortet. Ziel dieses Projekts ist es einerseits, neue algorithmische Methoden zur approximativen und exakten Lösung des Kreuzungszahlproblems zu entwickeln. Dabei kombinieren wir theoretische Forschung mit dem Konzept des Algorithm Engineering, um Verfahren zu erhalten die in der Praxis angewandt werden können. Andererseits betrachten wir auch andere Nichtplanaritätsmaße und möchten unsere Kreuzungszahlerfahrungen in neue algorithmische Verfahren für diese einfließen lassen. Dabei sei zum Beispiel das (ebenfalls NP-schwere) Problem des Maximum Planar Subgraph, sowie diverse Varianten wie Maximum Induced Planar Subgraph/Vertex Deletion Number oder Vertex Splitting Number explizit erwähnt. Diese Probleme treten in der Praxis häufig auf, stellen insbesondere bzgl. exakten und approximativen Verfahren jedoch gewichtige Herausforderungen dar.

Projektlaufzeit

  • 01.10.2018 - 30.09.2020

Schlagwörter

  • Theoretische Informatik

Organisationseinheit

Fach

Finanzierung durch

Bewilligungssumme

  • 204.279,56 €
Image Projekt-Links

Projektlinks


Image Projekt-Team

Projektteam


Sie sind Teil des Projektteams und möchten Inhalte ändern oder Projektergebnisse ergänzen? Kontaktieren Sie uns gerne unter fis@uni-osnabrueck.de