On Two-Dimensional Via Assignment for Single-Row Routing

H. C. Du, Oscar H. Ibarra, J. Fernando Naveda

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The wiring of multilayer boards is an important problem related to the fabrication of large electronic systems. The single-row routing approach has been proposed for solving this problem. This approach decomposes the original problem into several conceptually simpler subproblems. An important subproblem is the Via Assignment problem. In this subproblem, each net is decomposed into a number of row and column connections using a minimum number of vias. A number of algorithms have been proposed for this problem. However, only via columns or via rows–but not both–have been allowed in those studies, this problem is computationally intractable (i.e., NP-hard) even for which via columns as well as via rows are allowed. We have shown that the this problem is computationally intractable (i.e., NP-hard) even for the cases where only one via row and one via column are allowed [13]. Therefore, we propose heuristic algorithms for its solution. One of the proposed heuristic algorithms generates better results than previously proposed one-sided algorithms. That is, the total number of via rows plus via columns required by this algorithm is less than the number of rows or columns required by previously proposed algorithms. This algorithm is also found to be faster than previously proposed algorithms.

Original languageEnglish (US)
Pages (from-to)721-727
Number of pages7
JournalIEEE Transactions on Computers
Volume37
Issue number6
DOIs
StatePublished - Jun 1988

Bibliographical note

Funding Information:
Manuscript received August 22, 1985; revised July 16, 1986. This work was supported in part by NSF Grants MIP-8605297, MCS-83044756, DCR-8604603, and DCR-8420935, and by a grant from MEIS. H. C. Du and 0. H. Ibarra are with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. J. F. Naveda was with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. He is now with the Department of Computer Science, University of Kansas, Lawrence, KS. IEEE Log Number 8716234.

Keywords

  • Heuristic algorithms
  • NP-hard
  • multilayer board wiring
  • single-row routing
  • via assignment

Fingerprint Dive into the research topics of 'On Two-Dimensional Via Assignment for Single-Row Routing'. Together they form a unique fingerprint.

Cite this