15.10.2025, 9:45 Uhr
Universität Wien
Besprechungsraum 4.34
Währinger Str. 29
1090 Wien
Titel: Novel Methods in Utilizing Multivalued Decision Diagrams for
Solving Repetition-Free Longest Common Subsequence
Problems
Kurzfassung:
Diese Arbeit stellt eine verbesserte Version eines Algorithmus auf Basis mehrwertiger Entscheidungsdiagramme
(Multivalued Devision Diagram MDD) zur Lösung des Wiederholungsfreien Längsten
Gemeinsamen Teilsequenz-Problems (Repetition-Free Longest Common Subsequence RFLCS)
vor, bei dem die längste gemeinsame Teilsequenz zweier Zeichenketten ohne Wiederholungen von
Zeichen gesucht wird. Unser Ansatz integriert eine randomisierte Heuristik, die in der Praxis
konsistent optimale Lösungen findet, und nutzt MDDs auf neuartige Weise, um die Leistung
zu verbessern. Diese Neuerungen führen zu einer reduzierten Größe der MDDs und schnelleren
Laufzeiten. Umfangreiche Experimente zeigen Verbesserungen sowohl in der Lösungsqualität
als auch in der Effizienz über eine Vielzahl von Benchmark-Instanzen. Darüber hinaus löst
unsere Methode Instanzen, die bisher in der Literatur als ungelöst galten, und stellt somit einen
bedeutenden Fortschritt gegenüber bestehenden Ansätzen dar.