|
|||||
|
|
Optimal algorithms for adjacent side routing |
|
| Authors: | S. Alice Wu 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |