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 . 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.
Bibliographical noteFunding 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.
- Heuristic algorithms
- multilayer board wiring
- single-row routing
- via assignment