On a new timing-driven routing tree problem

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.