Optimal circuit clustering with variable interconnect delay

The paper aims at extending the circuit clustering algorithm of Rajaraman and Wong (1995) to handle a more sophisticated delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable in allowing the back-annotation of actual delay information to drive the clustering process. We first show that the original algorithm fails to produce optimal solutions for this delay model. In order to solve the problem, a generalized algorithm based on an extension of Rajaraman and Wong is proposed such that the problem can be solved optimally while the polynomial time complexity is maintained.