Optimal algorithms for adjacent side routing |
| |
| Authors: | S Alice Wu and Joseph JáJá |
| |
| Affiliation: | (1) Department of Electrical Engineering, University of Maryland, 20742 College Park, MD, USA;(2) Department of Electrical Engineering, Institue for Advanced Computer Studies and Systems Research Center, University of Maryland, 20742 College Park, MD, USA |
| |
| Abstract: | We consider the switchbox routing problem of two-terminal nets in the case when all thek nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.This research was supported in part by NSA Contract No. MDA-904-85H-0015, NSF Grant No. DCR-86-00378, and by NSF Engineering Research Centers Program NSFD CDR 88003012. |
| |
| Keywords: | VLSI routing Switchbox routing Algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
