{"id":{"repo_id":"odu","oai_identifier":"oai:digitalcommons.odu.edu:computerscience_etds-1165"},"canonical_url":"https://search.ndltd.org/etd/odu/oai:digitalcommons.odu.edu:computerscience_etds-1165","repository":{"repo_id":"odu","name":"Old Dominion University","base_url":"https://digitalcommons.odu.edu/do/oai/"},"display":{"title":"Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development","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.","abstract_html":"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 &quot;optimality&quot; and time performance characteristics. We fully implement one such algorithm, and experimentally show its superiority to previous routing heuristics.","abstract_has_math":false,"creators":["Hysom, David A."],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Stephen Olariu","David E. Keyes","Shunichi Toida","Stewart Shen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:29:47Z","subjects":["Heuristic programming","SRRP","VLSI design","Distribution","Probability theory","Digital Communications and Networking","Probability","Theory and Algorithms"],"languages":[],"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>"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.odu.edu/computerscience_etds/168","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.odu.edu/computerscience_etds/168","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.odu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.odu.edu%3Acomputerscience_etds-1165","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Stephen Olariu","David E. Keyes","Shunichi Toida","Stewart Shen"]},{"key":"dc:creator","label":"Author","values":["Hysom, David A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2023-10-25T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["1997-05-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Heuristic programming","SRRP","VLSI design","Distribution","Probability theory","Digital Communications and Networking","Probability","Theory and Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["<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>"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.odu.edu/computerscience_etds/168"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development"]}]}],"canonical_facts":{"dc:contributor":["Stephen Olariu","David E. Keyes","Shunichi Toida","Stewart Shen"],"dc:creator":["Hysom, David A."],"dc:date.available":["2023-10-25T07:00:00Z"],"dc:date.created":["1997-05-01T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.odu.edu/computerscience_etds/168"],"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>"],"dc:subject":["Heuristic programming","SRRP","VLSI design","Distribution","Probability theory","Digital Communications and Networking","Probability","Theory and Algorithms"],"dc:title":["Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:29:47Z"}