Coloring based approach for matching unrooted and/or unordered trees

dc.contributor.authorYahiaoui, Saïd
dc.contributor.authorHaddad, Mohammed
dc.contributor.authorEffantin, Brice
dc.contributor.authorKheddouci, Hamamache
dc.description.abstractWe consider the problem of matching unrooted unordered labeled trees, which refers to the task of evaluating the distance between trees. One of the most famous formalizations of this problem is the computation of the edit distance defined as the minimum-cost sequence of edit operations that transform one tree into another. Unfortunately, this problem has been proved to be NP-complete. In this paper, we propose a new algorithm to measure distance between unrooted unordered labeled trees. This algorithm uses a specific graph coloring to decompose the trees into small components (stars and bistars). Then, it determines a distance between two trees by computing the edit distance between their components. We prove that the proposed distance is a pseudo-metric and we analyze its time complexity. Our experimental evaluations on large synthetic and real world datasets confirm our analytical results and suggest that the distance we propose is accurate and its algorithm is scalable.
dc.relation.ispartofseriesPattern Recognition Letters; Vol. 34 - N° 6
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectEdit distance
dc.subjectGraph matching
dc.subjectUnrooted tree
dc.subjectUnordered tree
dc.titleColoring based approach for matching unrooted and/or unordered trees