Graph Optimal Monomorphism Algorithms

The characterization of graph morphisms in terms of the subgraphs of the Cartesian graph product is extended and used to develop algorithms for an optimal graph monomorphism problem. The objective functional considered is defined as the sum of the weights associated with vertex and arc mappings. A reduction algorithm is proposed to obtain sharp lower bounds on the value of the solution. The lower bounds are used in a branch-and-bound algorithm for the optimal graph monomorphism problem.