Detailansicht
Novel methods in utilizing multivalued decision diagrams for solving repetition-free longest common subsequence problems
Georg Braun
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Informatik
Betreuer*in
Kathrin Hanauer
Mitbetreuer*in
Maximilian Vötsch
DOI
10.25365/thesis.79366
URN
urn:nbn:at:at-ubw:1-24339.31727.907256-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit stellt eine verbesserte Version eines Algorithmus auf Basis mehrwertiger Entscheidungs-diagramme (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.
Abstract
(Englisch)
This work presents an enhanced version of an existing multivalued decision diagram (MDD) algorithm for solving the Repetition-Free Longest Common Subsequence (RFLCS) problem, which involves finding the longest subsequence common to two strings without repeated characters. Our approach combines a randomized heuristic that consistently achieves optimal solutions with minimal exceptions and an MDD utilized in a novel way. The new approaches applied to the MDD lead to better MDD growth behaviour and enhanced runtime efficiency. We employ extensive experiments and comparisons to demonstrate the superiority of our method, showing substantial gains in both solution quality and computational efficiency across a wide range of common problem instances for the problem. Furthermore, our approach successfully solves problem instances that were previously unsolved in the literature, marking a significant advancement in the field.
Schlagwörter
Schlagwörter
(Deutsch)
Wiederholungsfreie längste gemeinsamen Teilfolge Mehrwertiges Entscheidungsdiagramm Kombinatorische Optimierung Constraint-Programmierung Integer-Programmierung Exakte Algorithmen Randomisierte Heuristik NP-schweres Problem
Schlagwörter
(Englisch)
Repetition-Free Longest Common Subsequence Problem Multivalued Decision Diagram Combinatorial Optimization Constraint Programming Integer Programming Exact Algorithm Randomized Heuristic NP-Hard Problem
Autor*innen
Georg Braun 
Haupttitel (Englisch)
Novel methods in utilizing multivalued decision diagrams for solving repetition-free longest common subsequence problems
Paralleltitel (Deutsch)
Neue Methoden zur Nutzung von multivariaten Entscheidungsdiagrammen zur Lösung von wiederholungsfreien längsten gemeinsamen Teilsequenz-Problemen
Publikationsjahr
2025
Umfangsangabe
xiii, 49 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Kathrin Hanauer
AC Nummer
AC17650995
Utheses ID
76727
Studienkennzahl
UA | 066 | 921 | |