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.
|Number of pages
|Proceedings - IEEE International Symposium on Circuits and Systems
|Published - 1996
|Proceedings of the 1996 IEEE International Symposium on Circuits and Systems, ISCAS. Part 1 (of 4) - Atlanta, GA, USA
Duration: May 12 1996 → May 15 1996
ASJC Scopus subject areas
- Electrical and Electronic Engineering