A Distinctive O(mn) Time Algorithm for Optimal Buffer Insertions

Xinsheng Wang1,  Wenpan Liu1,  Mingyan Yu2
1Harbin Institute of Technology, 2Ningbo Institute of Technology Zhejiang University


Abstract

We have proposed an advanced algorithm to speed up the process of finding the optimal buffer solution of a wire tree. The algorithm time complexity is O(b2n+mn)for multi-pins. Simulation results have shown that our algorithm runs evidently faster than previous works for both 2-pin nets and multi-pin nets. In addition, as a fundamental algorithm, our achievement is applicable to some of the precious works.