An O(nlogn) time algorithm for optimal buffer insertion

The classic algorithm for optimal buffer insertion due to van Ginneken has time and space complexity O(n²), where n is the number of possible buffer positions. We present a new algorithm that computes the same optimal results, but in time and space complexity O(nlogn). Our speedup is achieved by four new ideas: an efficient data structure, the concept of buffer-dominate, a fast redundancy check, and a fast merging scheme. On industrial test cases, the new algorithm is 2 to 50 times faster than van Ginneken´s algorithm and uses 1/2 to 1/100 of the memory. Since van Ginneken´s algorithm and its variations are used by most existing algorithms on buffer insertion, buffer sizing, and wire sizing, our new algorithm significantly improves the performance of all these algorithms.