HS: a hierarchical search package for CAD data
N.P. Parikh, Chi-Yuan Lo, Anoop Singhal, Kaijie Wu · 1990
A hierarchical search software package that allows an application to retrieve flattened netlist data from a hierarchical netlist database. An algorithm is presented that implicitly searches the entire VLSI CAD net list data space without first constructing it. While traditional methods construct the entire search space explicitly, which helps to achieve a fast O(1) query time but requires Omega (n) space, this method relies on the circuit hierarchy to prune the search effectively. It is shown that the hierarchical net list data space is smaller by a factor of O(n/sup epsilon /). Where O>