loading...
An Algorithm for Finding a Non-Trivial Lower Bound for Channel Routing
Hyderabad, India January 04-January 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.1997.568200Tenth International Conference on VLS ...
 This Article 
 
PURCHASE ARTICLE: $0
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
R.K. Pal, S.P. Pal, A. Pal, "An Algorithm for Finding a Non-Trivial Lower Bound for Channel Routing," VLSI Design, International Conference on, pp. 531, Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, 1997.
 
 
BibTex
x
 
@article{ 10.1109/ICVD.1997.568200,
author = {R.K. Pal and S.P. Pal and A. Pal},
title = {An Algorithm for Finding a Non-Trivial Lower Bound for Channel Routing},
journal ={VLSI Design, International Conference on},
volume = {0},
year = {1997},
issn = {1063-9667},
pages = {531},
doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1997.568200},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - VLSI Design, International Conference on
TI - An Algorithm for Finding a Non-Trivial Lower Bound for Channel Routing
SN - 1063-9667
SP
EP
A1 - R.K. Pal,
A1 - S.P. Pal,
A1 - A. Pal,
PY - 1997
KW - VLSI
KW - three-layer restricted dogleg routing model
KW - nontrivial lower bound
KW - channel routing problem
KW - VLSI design
KW - two-layer Manhattan routing model
KW - polynomial time algorithm
KW - three-layer no-dogleg HVH routing model
KW - two-layer restricted dogleg routing model
KW - vertical constraint graph
VL - 0
JA - VLSI Design, International Conference on
ER -
 
R.K. Pal, Dept. of Comput. Sci., Calcutta Univ., India
S.P. Pal, Dept. of Comput. Sci., Calcutta Univ., India
A. Pal, Dept. of Comput. Sci., Calcutta Univ., India
Channel routing is a key problem in the physical design of VLSI chips. It is known that max(d/sub max,/v/sub max/) is a lower bound on the number of tracks required in the reserved two-layer Manhattan routing model, where d/sub max/ is the channel density and v/sub max/ is the length of the longest path in the vertical constraint graph. In this paper we propose a polynomial time algorithm that computes a better and non-trivial lower bound on the number of trades required for routing a channel without doglegging. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer no-dogleg HVH routing as well as two- and three-layer restricted dogleg routing models.
Index Terms:
VLSI, three-layer restricted dogleg routing model, nontrivial lower bound, channel routing problem, VLSI design, two-layer Manhattan routing model, polynomial time algorithm, three-layer no-dogleg HVH routing model, two-layer restricted dogleg routing model, vertical constraint graph
Citation:
R.K. Pal, S.P. Pal, A. Pal, "An Algorithm for Finding a Non-Trivial Lower Bound for Channel Routing," vlsid, pp.531, Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, 1997
Usage of this product signifies your acceptance of the Terms of Use.