Abstract. Graph pattern-matching is a generalization of string matching and two-dimensional pattern-matching that offers a natural framework for the study of matching problems upon multi-dimensional structures. We present in this paper an algorithm for pattern-matching on arbitrary graphs that is based on reducing the problem of finding a homomorphic image of a pattern graph in a target graph, to that of finding homomorphic images of every connected component of the pattern in the target. For every connected component, the algorithm performs a combinatorial search bounded by a pruning operator. The algorithm can be applied to directed graphs as well as to undirected graphs, and it can also be specialized to find isomorphic images only.
Full text. PDF file (193563 bytes).