On a new timing-driven routing tree problem

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

doi:10.1109/ISCAS.1996.541991

On a new timing-driven routing tree problem

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

^*Corresponding author for this work

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

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 language	English
Title of host publication	Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1996
Publisher	IEEE
Pages	420-423
Number of pages	4
ISBN (Print)	0780330730
DOIs	https://doi.org/10.1109/ISCAS.1996.541991
Publication status	Published - May 1996
Event	1996 IEEE International Symposium on Circuits and Systems, ISCAS 1996 - Atlanta, United States Duration: 12 May 1996 → 15 May 1996 https://ieeexplore.ieee.org/xpl/conhome/3834/proceeding

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Publisher	IEEE
ISSN (Print)	0271-4310

Conference

Conference	1996 IEEE International Symposium on Circuits and Systems, ISCAS 1996
Country/Territory	United States
City	Atlanta
Period	12/05/96 → 15/05/96
Internet address	https://ieeexplore.ieee.org/xpl/conhome/3834/proceeding

Scopus Subject Areas

Electrical and Electronic Engineering

Access to Document

10.1109/ISCAS.1996.541991

Cite this

@inproceedings{c9a9c02fe8624e7a9cba44140f23130f,

title = "On a new timing-driven routing tree problem",

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.",

author = "Chang, {Yao Wen} and Wong, {D. F.} and Kai Zhu and Wong, {C. K.}",

note = "This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459; 1996 IEEE International Symposium on Circuits and Systems, ISCAS 1996 ; Conference date: 12-05-1996 Through 15-05-1996",

year = "1996",

month = may,

doi = "10.1109/ISCAS.1996.541991",

language = "English",

isbn = "0780330730",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "IEEE",

pages = "420--423",

booktitle = "Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1996",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/3834/proceeding",

}

Chang, YW, Wong, DF, Zhu, K & Wong, CK 1996, On a new timing-driven routing tree problem. in Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1996. Proceedings - IEEE International Symposium on Circuits and Systems, IEEE, pp. 420-423, 1996 IEEE International Symposium on Circuits and Systems, ISCAS 1996, Atlanta, Georgia, United States, 12/05/96. https://doi.org/10.1109/ISCAS.1996.541991

TY - GEN

T1 - On a new timing-driven routing tree problem

AU - Chang, Yao Wen

AU - Wong, D. F.

AU - Zhu, Kai

AU - Wong, C. K.

N1 - This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459

PY - 1996/5

Y1 - 1996/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029708494&partnerID=8YFLogxK

U2 - 10.1109/ISCAS.1996.541991

DO - 10.1109/ISCAS.1996.541991

M3 - Conference proceeding

AN - SCOPUS:0029708494

SN - 0780330730

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - 420

EP - 423

BT - Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1996

PB - IEEE

T2 - 1996 IEEE International Symposium on Circuits and Systems, ISCAS 1996

Y2 - 12 May 1996 through 15 May 1996

ER -

On a new timing-driven routing tree problem

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this