Abstract
dc:descriptionGraph editing distance is a measure of similarity or dissimilarity between two graphs. In this work, the algorithms for calculating the editing distance of classical A * graphs and their optimizations are analyzed. The aim is to develop graph editing algorithms with different search tree bypass methods using Java programming language, to explain in detail how the graph editing distance calculation algorithm is implemented, and to compare the performance of these algorithms when implemented in the same way, only with different tree bypass order. . Also implement two different lower and upper bound calculation functions and compare their influence on the graph editing distance calculation speed and determine the maximum number of comparable graph vertices with different edge-to-peak ratios for each of the implemented algorithms using different lower and upper bound calculation functions. The paper also implements two different lower and upper bound calculation functions and compares their influence on the graph editing distance calculation speed, determines the maximum number of comparable graph vertices with different edge-to-peak ratios for each of the implemented algorithms using different lower and upper bound calculation functions. According to the tests performed with the developed algorithms? results, it can be understood that the tree bypass method has a greater influence on the speed of the algorithm and the number of graph vertices between which the algorithm can calculate the editing distance than various algorithm optimizations. Also, accurate algorithms for calculating the editing distance of graphs are difficult to apply both for graphs with a number of vertices greater than 20 and for graphs with many edges.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Čunichin, Vladimir,
- Contributors dc:contributor
-
- Radavičius, Irmantas
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD107116548&prefLang=en_US