A fuzzy attributed graph approach to subcircuit extraction problem

Fuzzy attributed graph (FAG) is not only widely used in the fields of image understanding and pattern recognition, but is useful to fuzzy graph matching problem. One of the applications of fuzzy graph matching is the subcircuit extraction problem. Subcircuit extraction problem is very important for VLSI testing, layout versus schematic (LVS) check, and circuit partition, etc. In this paper, fuzzy attributed graph (FAG) is first effectively applied to the subgraph isomorphism problem. And then we provide an efficient fuzzy attributed graph algorithm based on the solution to subgraph isomorphism for the subcircuit extraction problem. Similarity measurement makes a significant contribution to both the subgraph isomorphism problem and the subcircuit extraction problem.