Best Paper Award für Petra Mutzel

Für ihr gemeinsames Paper ``Crossing Number for Graphs with Bounded Pathwidth´´ erhielten die Autoren Therese Biedl (University of Waterloo), Markus Chimani (Universität Osnabrück), Martin Derka (University of Waterloo), und Petra Mutzel (TU Dortmund) den Best Paper Award auf der ``28th International Symposium on Algorithms and Computation´´ (ISAAC 2017). Das Bild zeigt die Übergabe des Preises an Petra Mutzel und Martin Derka.

Das Paper schlägt u.a. einen exakten Algorithmus zur Berechnung der Kreuzungszahl von maximalen Graphen mit Pfadweite 3. Weiterhin wurde für das Kreuzungszahlproblem ein 2-Approximationsalgorithmus für allgemeine Graphen mit Pfadweite 3 entwickelt und ein 4w^3-Approximationsalgorithmus für maximale Graphen mit beschränkter Pfadweite w. Hier ist der Link zum Preprint der ISAAC-Publikation auf ArXiv.

 
Last modified: 2018-04-01 10:46 (external edit)
DokuWikiRSS-Feed