Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Routing multiterminal nets around a rectangle
Gonzalez T., Lee S. IEEE Transactions on Computers35 (6):543-549,1986.Type:Article
Date Reviewed: Feb 1 1987

The authors of this paper present an O(nm) approximation algorithm which solves the problem of connecting m signal nets for a set of n terminals laying on the sides of a rectangle such that the total area is minimized. The solution generated by the algorithm has an area ≤.69MC *OPT, where OPT is the area of an optimal solution. Some of the nets are routed by a simple greedy strategy, while the others are handled by several different strategies. In this way, a nonempty set of feasible solutions is produced, from which one with least area is selected. The first steps of the algorithm and the proofs of some lemmata are based on results of [1]; it would be useful to read that paper first.

Reviewer:  D. Seese Review #: CR110927
1) LaPaugh, A. S.Algorithms for integrated circuit layout, an analytic approach, PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA, 1980.
Bookmark and Share
 
Routing And Layout (F.2.2 ... )
 
 
Interconnection Architectures (C.1.2 ... )
 
 
Network Communications (C.2.1 ... )
 
 
Network Problems (G.2.2 ... )
 
 
Path And Circuit Problems (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Routing And Layout": Date
An improved solution to the traveling salesman problem with thousands of nodes
Litke J. Communications of the ACM 27(12): 1227-1236, 1984. Type: Article
Jul 1 1985
Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks
Leighton F., MIT Press, Cambridge, MA, 1983. Type: Book (9780262121040)
Mar 1 1985
Routing through a rectangle
Mehlhorn K. (ed), Preparata F. Journal of the ACM 33(1): 60-85, 1986. Type: Article
Sep 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy