An algorithm for graph optimal monomorphism

An algorithm for finding the optimal monomorphism between two attributed graphs is proposed. The problem is formulated as a tree search problem. To guide the search, the branch-and-bound heuristic approach is adopted, using an efficient consistent lower bounded estimate for the evaluation function of the cost associated with the optimal solution path in the search tree. This algorithm is a generalization of an algorithm for graph optimal isomorphism which has been compared with another algorithm for its performance. The present algorithm’s potential of engineering application is demonstrated by a simple structural pattern recognition problem and a plant allocation and distribution problem.