On a new timing-driven routing tree problem
Journal
Proceedings - IEEE International Symposium on Circuits and Systems
Journal Volume
4
Pages
420-423
Date Issued
1996
Author(s)
Abstract
In this paper, we consider a new model of timing-driven routing, based on the idea of finding minimum spanning trees (minimum routing cost) with bounded delays, in a multiple weighted graph. This problem is originally motivated by the timing-driven routing for FPGA's, and is applicable to other related problems in which multiple independent optimization objectives need to be considered simultaneously. We prove that this problem in general is NP-complete, and there exists no approximation algorithm with any constant bound for the problem if the triangle inequality does not hold. We give approximation algorithms with a guaranteed performance bound for the case where the routing cost satisfies the triangle inequality. Experimental results show that our algorithms are very promising.
Other Subjects
Algorithms; Approximation theory; Computational complexity; Gates (transistor); Graph theory; Logic circuits; Mathematical models; Optimization; Switching functions; VLSI circuits; Approximation algorithm; Bounded delays; Field programmable gate arrays; Independent optimization objectives; Minimum routing cost; Minimum spanning trees; Timing driven routing tree problem; Circuit theory
Type
conference paper