A classical way of matching relational structures consists of finding a maximum clique in a derived "association graph". However it is not clear how to apply this approach to problems where the graphs are hierarchically organized, i.e., are trees, since maximum cliques are not constrained to preserve the partial order. We have recently provided a solution to this problem by constructing the association graph using the graph-theoretic concept of connectivity. In this paper we extend the approach to the problem of matching attributed trees. Specifically we show how to derive a "weighted" association graph, and prove that the attributed tree matching problem is equivalent to finding a maximum weight clique in it. We then formulate the maximum weight clique problem in terms of a continuous optimization problem, which we solve using "replicator" dynamical systems developed in theoretical biology. This formulation is attractive because it can motivate analog and biological implementations. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.
Attributed tree matching and maximum weight cliques
1999-01-01
141721 byte
Conference paper
Electronic Resource
English
Attributed Tree Matching and Maximum Weight Cliques
British Library Conference Proceedings | 1999
|Attributed hypergraph matching on a Riemannian manifold
British Library Online Contents | 2014
|Extended Attributed String Matching for Shape Recognition
British Library Online Contents | 1998
|Region Correspondence by Inexact Attributed Planar Graph Matching
British Library Conference Proceedings | 1995
|On the Problem of Attributed Relational Graph Matching
British Library Online Contents | 1992
|