A new heuristic for single row routing problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new heuristic for single row routing problems

Full text

Pdf (559 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 26th ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 167 - 172

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

N. A. Sherwani	Department of Computer Science, Western Michigan University, Kalamazoo, MI
J. S. Deogun	Department of Computer Science, University of Nebraska-Lincoln, Lincoln, NE

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS\TCDA : TC Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 12, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/74382.74411 What is a DOI?

ABSTRACT

In this paper, we present a new heuristic algorithm for the classical single row routing problem. The algorithm is based on a graph theoretic decomposition scheme and uses modified cut-numbers. The algorithm was implemented in C on VAX 8200. The experimental results show that the quality of solutions generated by our algorithm could be up to 36% better as compared to the existing algorithms.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. B. Bhattacharya, J. S. Deogun and N. A. Sherwani, "A Graph Theoretic Approach to Single Row Routing Problems," The Proc. 1988 IEEE Int. Symp. Circuits and Syst., June 6-9, Espoo, Finland.
	2	David Hung-Chang Du , Lee-Chin Hsu Liu, Heuristic algorithms for single row routing, IEEE Transactions on Computers, v.36 n.3, p.312-321, March 1987 [doi>10.1109/TC.1987.1676903]
	3	E. S. Kuh, T. Kashiwabara, and T. Fujisawa, "On optimum single row routing," IEEE Trans. Circuits Syst., vol. CAS-26, pp. 361-368, June 1979.
	4	R. Raghavan and S. Sahni, "Single row routing," IEEE Trans. Comput., vol. C-32, pp. 209-220, Mar. 1983.
	5	R. Raghavan and S. Sahni, "Complexity of single row routing problems," IEEE Trans. Circuits Syst., vol. CAS-31, no. 5, pp. 462-471, May 1984.
	6	H. C. So, "Some theoretical results on the routing of multilayer printed-wiring boar.:ls," in Proc. 197~ IEEE Int. Syrup. Circuits and Syst., pp. 296- 303.
	7	B. S. Ting, E. S. Kuh, and I. Shirakawa, "The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single row, single layer case," IEEE Trans. Circuits Syst., vol. CAS- 23. pp. 768-778, Dec. 1976.
	8	T. T. K. Trang, M. Marek-Sadowska, and E. S. Kuh, "An efficient single-row routing algorithm," IEEE Trans. Comput.-Aided Des., vol. CAD-3, pp. 178-183, July 1984.