Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Engineering
Single Row Routing: Theoretical And Experimental Performance Evaluation, And New Heuristic Development, David A. Hysom
Single Row Routing: Theoretical And Experimental Performance Evaluation, And New Heuristic Development, David A. Hysom
Computer Science Theses & Dissertations
The Single Row Routing Problem (SRRP) is an abstraction arising from real-world multilayer routing concerns. While NP-Complete, development of efficient SRRP routing heuristics are of vital concern to VLSI design. Previously, researchers have introduced various heuristics for SRRP; however, a comprehensive examination of SRRP behavior has been lacking.
We are particularly concerned with the street-congestion minimization constraint, which is agreed to be the constraint of greatest interest to industry. Several theorems stating lower bounds on street congestion are known. We show that these bounds are not tight in general, and argue they may be in error by at least 50% …