On the optimization of MOS circuits

Optimizing the number of transistors in a complex MOS gate, which is important for minimizing chip area and delay in VLSI designs, is an NP-complete problem. The worst-case computational complexity of graph-oriented algorithms used in existing approaches is exponential in the number of transistors. This problem is addressed through the use of bridging switches. A theory and an algorithm for optimization of MOS switch networks using an edge-merging technique are proposed. The worst-case computational complexity of the heuristic algorithm proposed is O(n⁵e²), where n is the number of nodes and e is the number of edges in the switch network