An efficient subcircuit extraction algorithm by resource management

To find subcircuits in a larger electronic circuit continues to be important in the test of VLSI computer-aided design and IC fabrication or verification. In this paper, an efficient approach to solve the subgraph isomorphism problem based on the resource management paradigm is transformed to extract subcircuits. By integrating several effective planning strategies with the concept of centered spanning tree for circuit decomposition and partition, the proposed approach minimizes the number of backtracks and eliminates the nonisomorphic subcircuits early during the tree and cotree matching process, so that the time wasted on unsuccessful matching is dramatically reduced. Thus, an average-case, near-linear time performance is achieved, even in cases where the circuit size is very large and the circuit structure is highly symmetric. Also, due to the graphic representation of circuits with preservation of the topological structure information, the shorted input circuits which are intractable to SubGemini can be recognized without difficulty