On isomorphisms of attributed relational graphs for pattern analysis and a new branch and bound algorithm

The problem of isomorphisms of attributed relational graphs (IARG) is discussed for pattern analysis. The problem of IARG is formulated into the problem of optimal path search (OPS) of state space. Emphasis is on the proof of the equivalence between IARG and OPS. The direct result of the proof is that relatively concrete form of the function h^*(u) is obtained which is the cost of an optimal path from the state u to a goal state. A consistent lower-bounded estimate h(u) of h^*( u)P is proposed, and that h(u) has an advantage over hˆ(u) which is a consistent lower-bounded estimate of h^*(u) is proved