A “GGreedy” channel router

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A “GGreedy” channel router

Full text

Pdf (773 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Papers on Twenty-five years of electronic design automation table of contents

Pages: 256 - 262

Year of Publication: 1988

ISBN:0-89791-267-5

Authors

R. L. Rivest	MIT Laboratory for Computer Science, Cambridge, Mass., and GE Research and Development Center, Schenectady, New York
C. M. Fiduccia	MIT Laboratory for Computer Science, Cambridge, Mass., and GE Research and Development Center, Schenectady, New York

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 5, Citation Count: 1

Additional Information:

references cited by 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/62882.62912 What is a DOI?

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.

	Al80	Alford, S. "DYCHAR: A Channel Router which uses dynamic channel assignment," MIT Bachelor's thesis. (M y 198o).
	AKT76	Asano, T., T. Kitahashi, and K. Tauaka, "On a Method of Realizing Minimum-Width Wiring," Electronics and Communications in Japan, Vol. J59-A, No. 2 (1976), 29-39.
	BR81	Brown, D. and R. L. Rivest, "New Lower Bounds on Channel Width", Proc. CMU Conference on VLSI Systems and Computations, (Computer Science Press 1981) 178-185.
	De76	David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
	DKSSU81	Danny Dolev , Kevin Karplus , Alan Siegel , Alex Strong , Jeffrey D. Ullman, Optimal wiring between rectangles, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.312-317, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802484]
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	Ha71	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
	Hi74	ttightower, D., "The {nterconncction Problem: A Tutorial," Computer 7,4 (April 1974), 18-32.
	KK79	Tatsuya Kawamoto , Yoji Kajitani, The minimum width routing of A 2-row 2-layer polycell-layout, Proceedings of the 16th Conference on Design automation, p.290-296, June 25-27, 1979, San Diego, CA, United States
	KSP73	B. W. Kernighan , D. G. Schweikert , G. Persky, An optimum channel-routing algorithm for polycell layouts of integrated circuits, Proceedings of the 10th workshop on Design automation, p.50-59, June 25-27, 1973
	Ko81	Koschella, J., "A Placement/interconnect Channel Router: Cutting your PI into Slices," Bachelor's Thesis. M1T Department of Electrical Engineering and Computer Science. (May 1981).
	La80	A. S. LaPaugh, ALGORITHMS FOR INTEGRATED CIRCUIT LAYOUT: AN ANALYTIC APPROACH, Massachusetts Institute of Technology, Cambridge, MA, 1980
	Le81	Leighton, T., "New Lower Bounds for Channel Routing," To appear.
	LP81	Leiserson, C., and R. Pinter, "Optimal Placement for River Routing," Proc. CMU Conference on VLSI Systems and Computations, (Computer Science Press 1981), 126-143.
	PDS77	Persky, G., D. Deutsch, and D. Schweikert, "LTX - A Minicomputer-Based System for Automated LSt Layout," Journal of Design Automatic~ and Fault- Tolerant Computing 1,3 (May 1977), 217-255.
	Pi81	Pinter, R., "Optimal Routing in Rectilinear Channels," Proc. CAJU Conference on VI, SI System, s and Computations, (Computer Sc(ence Press 1981), t60- 177.
	Ri81a	!:elves't, R. L., " '13enchlnark' Channel-l~:ollting Problems," In preparation.
	Ri82	Ronald L. Rivest, The “PI” (placement and interconnect) system, Proceedings of the 19th conference on Design automation, p.475-481, January 1982
	RBM81	t~ivest,, R. L., A. g. Baratz, and G. Miller, "Provably Good Channel-lloutillg Algorithms," Proc. CMU Conference on VLSI Systems a r~,t Computations, (Computer Science Press 1981), 153-159.
	SB80	Sartaj Sahni , Atul Bhatt, The complexity of design automation problems, Proceedings of the 17th conference on Design automation, p.402-411, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804562]
	So81	Soukup, J., "Circuit Layout," Proc. of the IEEE, Vol. 69, No. 10(Oct. 1981), 1281-130,1.
	Sz81	Szymanski, T., "Dogleg Channel Routing is NP- Complete," To appear.
	To80	Martin Tompa, An optimal solution to a wire-routing problem (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.161-176, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804664]
	YK80	Yoshimura, T. and E. Kuh, "Eltqcient Algorithms for Channel I-~out.iug," U. C. Berkeley Electronics l'~esearch Laboratory Memo. No. M80/43 (August, 1980).