Optimal algorithms for adjacent side routing

TitleOptimal algorithms for adjacent side routing
Publication TypeJournal Articles
Year of Publication1991
AuthorsWu SA, JaJa JF
JournalAlgorithmica
Volume6
Issue1
Pagination565 - 578
Date Published1991///
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.

DOI10.1007/BF01759060