| |
Abstract:
Motivated by our recent work on rooted tree matching, in this
paper we provide a solution to the problem of matching two free
(i.e., unrooted) trees by constructing an association graph whose
maximal cliques are in one-to-one correspondence with maximal
common subtrees. We then solve the problem using simple
replicator dynamics from evolutionary game theory. Experiments on
hundreds of uniformly random trees are presented. The results are
impressive: despite the inherent inability of these simple
dynamics to escape from local optima, they always returned a
globally optimal solution.
|
