Back to search

Institutional Repository of Vilnius University

Grafų redagavimo atstumas /

Abstract

dc:description

Graph 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Čunichin, Vladimir,. Grafų redagavimo atstumas /. Institutional Repository of Vilnius University, 2021. https://repository.vu.lt/VU:ELABAETD107116548&prefLang=en_US