Heuristic Algorithms for Single Row Routing

David Lee Chin Hsu Du, Lee Chin Hsu Liu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

A heuristic algorithm, based on the criterion of having nets with larger cut numbers assigned to inner tracks and nets with smaller cut numbers assigned to outer tracks, for single row routing problem has recently been proposed by Tarng et al. It has been reported that this algorithm has always been able to produce the optimal solutions for all the examples tested so far. In this paper, we have proved that algorithms based on the heuristic criterion of cut numbers produce optimal solutions for instances in which all nets cover at least one common node (i.e., form a single group). However, the algorithm proposed by Tarng et al. may not produce optimal solutions for instances of multiple net groups. Thus, several possible heuristic algorithms based on the same criterion, but also taking into consideration the net grouping situation have been proposed. The experimental results show that the proposed algorithms are faster and often generate better results than the one proposed by Tarng et al. A tighter lower bound on the number of tracks required is also obtained in this paper.

Original languageEnglish (US)
Pages (from-to)312-320
Number of pages9
JournalIEEE Transactions on Computers
VolumeC-36
Issue number3
DOIs
StatePublished - Mar 1987

Fingerprint Dive into the research topics of 'Heuristic Algorithms for Single Row Routing'. Together they form a unique fingerprint.

Cite this