Back to search

Old Dominion University

Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development

Abstract

dc:description.abstract

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% for some problem instances. On an experimental level, we examine upper and lower bound behavior through generation and processing of large data sets of randomly distributed problem instances. Using this data as input to implementations of previously published heuristics, we establish a minimal performance baseline for evaluation of routing algorithms. We also present a new algorithmic framework, and discuss its use for development of heuristics of varying "optimality" and time performance characteristics. We fully implement one such algorithm, and experimentally show its superiority to previous routing heuristics.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hysom, David A.
Contributors dc:contributor
  • Stephen Olariu
  • David E. Keyes
  • Shunichi Toida
  • Stewart Shen

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Old Dominion University
Base URL
digitalcommons.odu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hysom, David A.. Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development. Thesis thesis, https://digitalcommons.odu.edu/computerscience_etds/168