Efficient parallel branch-and-bound approaches for exact graph edit distance problem

Simple item page
dc.contributor.authorDabah, Adel
dc.contributor.authorChegrane, Ibrahim
dc.contributor.authorYahiaoui, Saïd
dc.contributor.authorBendjoudi, Ahcene
dc.date.accessioned2023-02-26T08:49:26Z
dc.date.available2023-02-26T08:49:26Z
dc.date.issued2022-12
dc.description.abstractGraph Edit Distance (GED) is a well-known measure used in the graph matching to measure the similarity/dissimilarity between two graphs by computing the minimum cost of edit operations needed to transform one graph into another. This process, Which appears to be simple, is known NP-hard and time consuming since the search space is increasing exponentially. One way to optimally solve this problem is by using Branch and Bound (B&B) algorithms, Which reduce the computation time required to explore the whole search space by performing an implicit enumeration of the search space instead of an exhaustive one based on a pruning technique. nevertheless, They remain inefficient when dealing with large problem instances due to the impractical running time needed to explore the whole search space. To overcome this issue, We propose in this paper three parallel B&B approaches based on shared memory to exploit the multi-core CPU processors: First, a work-stealing approach where several instances of the B&B algorithm explore a single search tree concurrently achieving speedups up to 24 faster than the sequential version. Second, a tree-based approach where multiple parts of the search tree are explored simultaneously by independent B&B instances achieving speedups up to 28. Finally, Due to the irregular nature of the GED problem, two load-balancing strategies are proposed to ensure a fair workload between parallel processes achieving impressive speedups up to 300. all experiments have been carried out on well-known datasets
dc.identifier.issn0167-8191
dc.identifier.urihttps://dl.cerist.dz/handle/CERIST/966
dc.publisherElsevier
dc.relation.ispartofseriesParallel Computing; Vol. 114
dc.relation.pages1-15
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectParallel branch-and-bound
dc.subjectGraph matching
dc.subjectGraph edit distance
dc.titleEfficient parallel branch-and-bound approaches for exact graph edit distance problem
dc.typeArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Efficient parallel branch-and-bound approaches for exact graph edit distance problem.pdf
Size:
1.24 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
International Journal Papers