In some applications of matching, the structural or hierarchical properties of the two graphs being aligned must be maintained. The hierarchical properties are induced by the direction of the edges in the two directed graphs. These structural relationships defined by the hierarchy in the graphs act as a constraint on the alignment. In this paper, we formalize the above problem as the weighted alignment between two directed acyclic graphs. We prove that this problem is NP-complete, show several upper bounds for approximating the solution, and finally introduce polynomial time algorithms for sub-classes of directed acyclic graphs.
ABSURDIST II, an extension to ABSURDIST, is an algorithm using attributed graph matching to find translations between conceptual systems. It uses information about the internal structure of systems by itself, or in combination with external information about concept similarities across systems. It supports systems with multiple types of weighted or unweighted, directed or undirected relations between concepts. The algorithm exploits graph sparsity to improve computational efficiency. We present the results of experiments with a number of conceptual systems, including artificially constructed random graphs with introduced distortions.