Detailansicht
Engineering maximum common subgraph algorithms for large graphs
Jonathan Trummer
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
Nils Morten Kriege
Mitbetreuer*in
Kathrin Hanauer
DOI
10.25365/thesis.70709
URN
urn:nbn:at:at-ubw:1-11248.12864.832018-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Problem des Größten Gemeinsamen Subgraphen sucht den größten Subgraphen, den zwei gegebene Graphen beinhalten.
Dieses Problem lässt sich in vielen verschiedenen Forschungsfeldern anwenden, so kann damit zum Beispiel die größte gemeinsame Struktur zweier Moleküle bestimmt werden, was in den Bereichen der Chemie, Molekular Wissenschaften und Computer-gestützter Medikamenten-Entwicklung angewandt werden kann. Da das Problem NP-vollständig ist, lässt sich eine optimale Lösung nicht direkt berechnen, sondern der gesamte Lösungsraum muss abgesucht werden. Es wurden bereits verschiedene Ansätze angewandt, um Lösungen für das Problem des Größten Gemeinsamen Subgraphen zu finden. Dazu zählt eine Reduktion zum Problem der größten Clique, beziehungsweise zum Problem der kleinsten Knotenüberdeckung, sowie eine Formulierung als Bedingungserfüllungsproblem und Ansätze, die den Lösungsraum partitionieren.
Wir präsentieren zwei Methoden der Datenreduktion, welche genutzt werden können, um die Größe der Eingabe-Graphen zu reduzieren und somit die Lösungssuche zu vereinfachen. Weiteres präsentieren wir zwei Ansätze um obere Schranken für die Lösungsgröße zu berechnen, welche genutzt werden können, um die Suche im Lösungsraum früher zu beenden.
Zusätzlich untersuchen wir das Ausnutzen von Symmetrien im Lösungsraum, um den Lösungsraum zu verkleinern.
Wir untersuchen weiters die Anwendung eines Algorithmus zur Findung von einer größten stabilen Menge als Alternative zu bestehenden Lösungsansätzen. In unserer experimentellen Auswertung untersuchen wir diese Techniken und zeigen, dass ein heuristischer Algorithmus für stabile Mengen existierende Algorithmen sowohl in Bezug auf Laufzeit als auch in Bezug auf Ergebnisqualität überbieten kann, wenn die Laufzeit per Eingabe-Graphen limitiert wird. Weiters präsentieren und untersuchen wir eine Vorverarbeitungs-Phase für einen existierenden Algorithmus, welche für eine Gruppe an Eingabe-Graphen in der Lage ist, die Laufzeit um über 80% zu reduzieren.
Abstract
(Englisch)
The Maximum Common Subgraph problem is to find the largest subgraph common to two given graphs. This problem finds applications in a wide variety of fields, for example it can be utilized to find common substructures between two molecules, which may be useful in the fields of chemistry, molecular science and computational drug discovery.
As the problem is NP-complete, finding an optimal solution requires exhaustively exploring the solution space. Various different approaches have been applied to the Maximum Common Subgraph problem, such as reducing it to the Maximum Clique or Minimum Vertex-Cover problems, applying Constraint-Satisfaction Programming or utilizing a partitioning approach. We propose two methods of data reduction, which may be used to reduce the sizes of the input graphs and can thus simplify the problem.
Additionally, we propose two methods of computing upper bounds, as means to terminate the search for solutions as soon as the best solution found matches the upper bound.
We explore the exploitation of symmetries, as to reduce the search space which needs to be explored, and we evaluate an Independent Set solver as an alternative solver.
Finally, we extensively evaluate existing approaches and our techniques experimentally, where we show that a heuristic independent set solver may significantly outperform existing approaches both in terms of running time as well as result quality, given a maximum execution time per problem instance.
We additionally introduce a pre-processing phase for a partitioning-based solver, which is able to reduce the running time on instances of one instance group by over 80%.
Schlagwörter
Schlagwörter
(Englisch)
Maximum Common Subgraph Algorithm Engineering Large Graphs
Schlagwörter
(Deutsch)
Größter Gemeinsamer Subgraph Algorithmen Entwicklung Große Graphen
Autor*innen
Jonathan Trummer
Haupttitel (Englisch)
Engineering maximum common subgraph algorithms for large graphs
Paralleltitel (Deutsch)
Entwicklung von Algorithmen zur Lösung des Größten Gemeinsamen Subgraphen-Problems in großen Graphen
Publikationsjahr
2021
Umfangsangabe
viii, 83 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Nils Morten Kriege
AC Nummer
AC16503536
Utheses ID
61048
Studienkennzahl
UA | 066 | 921 | |