Masterarbeit

Beschreibung:

Storyline Zeichnungen werden benutzt, um die Beziehungen von Charakteren eines Filmes zu visualisieren. Hierbei wird jeder Akteur als eine x-monotone Kurve dargestellt. Die x-Achse symbolisiert den zeitlichen Verlauf im Film. Zwei Charaktere sollen nah beieinander sein, wenn Sie auch in der Handlung interagieren. Man möchte solche Zeichnungen mit möglichst wenig Kreuzungen erstellen. Ein wünschenswertes Kriterium beim Zeichnen dieser Graphen ist es, Kreuzungen zu vermeiden. Das Berechnen der minimalen Anzahl der Kreuzungen ist ein NP-schweres Problem. Es gibt jedoch Algorithmen die dieses Problem lösen. Sie sollen einen kürzlich vorgestellten FPT Algorithmus implementieren und dessen Laufzeit mit einer bekannten Lösung durch ein Ganzzahliges Lineares Programm vergleichen. Zudem soll versucht werden, den FPT Algorithmus zu optimieren und Methoden zu entwickeln, die dessen Speicherverbrauch verbessern.