An improved layout verification algorithm (LAVA)

The correctness of a VLSI circuit layout can be verified by comparing the netlist extracted from the layout with the specification netlist. Ebeling and Zajicek (1983) showed that this problem can be solved by utilizing known techniques for solving the classical graph isomorphism problem. The authors present an improved algorithm for solving the graph isomorphism problem associated with layout verification. This algorithm takes advantage of the bipartite nature of the graphs associated with the layout verification problem. The sum of the improvements in this algorithm tends to relieve the memory-intensive problems and accelerate the process