| The Sub-Graph Isomorphism (SGI) problem is of theoretical interest due to its well-known NP-complete complexity and is also of considerable practical importance since it occurs frequently in many applications. Previous approaches for solving this problem, including tree-search and nonlinear optimization, have either suffered from a lack of speed and accuracy or are trapped in the dilemma of memory utilization. No efficient algorithm for this problem is known as yet, and no practically acceptable results have been reported in research literature.; To fill this blank, a novel approach is uniquely developed in this dissertation. In contrast to the conventional tree-search approaches, the developed approach internally runs within a flexible planning mechanism based on the Constrained Resource Planning model. By fully integrating the principles of resource-sharing and utilization, and incorporating the set of powerful heuristic strategies, this planning-based approach can efficiently solve the SGI problem over a broad scope of inputs.; A theoretical and experimental analysis of the computational complexity of the developed SGI algorithm is demonstrated in this dissertation. The analytical study provides the time complexity in the worst and best cases, and the empirical investigation exhibits the implementation performance on average. The result shows not only the efficacy and effectiveness, but also the predictability and scalability of the developed SGI algorithm.; This efficient algorithm has demonstrated its capability on solving the practical SGI problems. For the problem of subcircuit extraction, the global and flexible mapping focus--Edge Unit, which is one edge associated with its two terminal nodes, can preserve the connection information of circuits in netlist representation. Consequently, the long-standing problem in circuit design automation--correct recognition of the logic devices with shorted external connections--is successfully solved, while the existing SGI algorithms have only narrow applicability due to the inherent limitation on their fundamental mapping approaches. This achievement will assist the circuit designers on the optimization of pattern library and the completion of advanced design tool-kits. |
