Algorithms for maximal common subgraph problem using resource planning

Graph matching (GM) is not only theoretically interesting but also practically important, as it is an essential technique for pattern recognition. The coverage of GM ranges from the simpler problems of Graph Isomorphism (GI) and Sub-Graph Isomorphism. (SGI) to the most complex forms of Maximal Common Subgraph (MCS) and Maximal Overlap Sets (MOS). In a unifying perspective, both GI and SGI are sub-problems of MCS. On the other hand, the overwhelming difficulty of solving MCS or MOS is due to not knowing what the largest matching pattern is, which leads to the NP-hardness of MCS and MOS.; Both MCS and MOS can be transformed into the equivalent problem of finding the Maximum Clique (MC) of the “correspondence graph” of the two inputs to MCS, or MOS. On the other hand, MC has a dual partner problem of graph coloring (GC) that is related by the well known fact that the minimum number of colors needed is always greater than or equal to the size of the maximum clique. Such mutually constraining bounds actually provide useful means for computation, in which MC and GC form a tightly coupled loop where one solution feeds into the other problem and vice versa, until (hopefully) the two bounds meet and the optimal solution is found for both problems. A novel algorithm is developed and tested in this dissertation work, performing this loop iteration and solution feedback until convergence or possibly some cut-off conditions. The solution of MC for the correspondence graph of the input graphs then provides a solution for the corresponding MCS (or MOS) problem.; In order to solve the MC and GC within the iterative loops, a resource management approach, known as ‘Constrained Resource Planning ’ (CRP), is applied as a method of optimization for obtaining intermediate solutions of MC and GC. The effectiveness of the developed CRP-GM algorithm is demonstrated with numerous standard benchmark graphs and several important application domains, including Protein commonality extraction and 3D object modeling from 2D views. The capacity of discovering hidden common patterns using the developed algorithm opens an entirely new spectrum of pattern discovery or data mining applications.