On a new timing-driven routing tree problem

Yao Wen Chang, D. F. Wong, Kai Zhu, C. K. Wong

Research output: Contribution to journalConference article

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.

Original languageEnglish (US)
Pages (from-to)420-423
Number of pages4
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume4
StatePublished - Jan 1 1996
Externally publishedYes
EventProceedings of the 1996 IEEE International Symposium on Circuits and Systems, ISCAS. Part 1 (of 4) - Atlanta, GA, USA
Duration: May 12 1996May 15 1996

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'On a new timing-driven routing tree problem'. Together they form a unique fingerprint.

  • Cite this