|
Katharina Zahnweh Mentor: Prof. Dr. Anusch Taraz
Stipendien und Auszeichnungen
Zurzeit beschäftige ich mich mit Graphendistanzen. Dabei hat man eine Klasse von Graphen gegeben und definiert nun eine Distanzfunktion zwischen je zwei Graphen, mit der man angeben will, wie stark man einen Graphen verändern muss, um einen anderen zu erhalten. Mögliche Veränderungen sind z.B. das Löschen, Einfügen und Umbenennen von Knoten und Kanten. Die sogenannte Edit-Distanz misst dann die Anzahl der Schritte, die man mindestens braucht, um den einen Graph mit den genannten Veränderungen in den anderen zu überführen. Die Berechnung der Edit-Distanz ist NP-schwer, es gibt aber auch andere Distanzen auf gewissen Graphen, die sich in polynomieller Zeit berechnen lassen. Ich möchte mich mit Distanzen zwischen bestimmten Bäumen beschäftigen. Die Berechnung der Distanz zweier Graphen ist z.B. bei der Erkennung von Mustern in der Bildverarbeitung oder in der Biologie wichtig. |
|
TopMath
