Efficient approximate approach for graph edit distance problem

Simple item page
dc.contributor.authorDabah, Adel
dc.contributor.authorChegrane, Ibrahim
dc.contributor.authorYahiaoui, Saïd
dc.date.accessioned2023-02-26T08:12:54Z
dc.date.available2023-02-26T08:12:54Z
dc.date.issued2021-11
dc.description.abstractGraph Edit Distance (GED) problem is a well-known tool used to measure the similarity/dissimilarity between two graphs. It searches for the best set of edit operations (in terms of cost) that transforms one graph into another. Due to the NP-hardness nature of the problem, the search space increases exponentially making exact approaches impossible to use for large graphs. In this context, there is a huge need for approaches that give near-optimal results in reasonable time. In this paper, we propose a tree-based approximate approach for dealing with GED problem. It operates on a search tree that models all possible solutions of the problem. Since exploring the whole tree is impractical; this approach keeps only the best nodes at each level of the tree for further exploration. This reduces enormously the execution time without scarifying the solution quality. Experiments using small and medium size data-sets show the low deviation of our results as compared to the optimal results of a Depth First Search algorithm. Moreover, our approach show a strong scalability potential by dealing with large data-sets in low execution time.
dc.identifier.issn0167-8655
dc.identifier.issn1872-7344
dc.identifier.urihttps://dl.cerist.dz/handle/CERIST/963
dc.publisherElsevier
dc.relation.ispartofseriesPattern Recognition Letters; Volume 151
dc.relation.pages310-316
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectGraph matching
dc.subjectGraph edit distance
dc.subjectApproximate approach
dc.subjectPattern recognition
dc.titleEfficient approximate approach for graph edit distance problem
dc.typeArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Efficient approximate approach for graph edit distance problem.pdf
Size:
669.22 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
International Journal Papers