Boots – shoes – and leggings
Patent
1993-10-04
1996-02-13
Teska, Kevin J.
Boots, shoes, and leggings
364488, 364489, 364490, G06F 1750, G06F 1500
Patent
active
054916410
ABSTRACT:
An apparatus and method for locating a good approximation of optimal Steiner tree routing in the presence of rectilinear obstacles, including finding a Steiner tree on an escape graph. The escape graph is constructed by forming lines from given points (pins) and obstacles. Obstacles and the segments of obstacles are provided with lines parallel to that segment at a given minimum distance S.sub.min from the obstacle. The lines are constructed until they reach either a boundary of an obstacle or a boundary of the core. For pins which do belong to a boundary of an obstacle, a ray, perpendicular to the segment of the boundary on which the pin is located is constructed from the pin and out from the obstacle until it reaches another obstacle or a boundary of the core. For pins which do not belong to an obstacle, vertical and horizontal lines are constructed. A Steiner tree may then be found on the escape graph by using any number of algorithms such as algorithm S and algorithm M. The solution to the problem of finding a Steiner tree for the escape graph also provides a suitable approximation of a Steiner tree for the original problem. This apparatus or method may be used to optimize the routing of conductive paths on integrated circuits.
REFERENCES:
patent: 4855929 (1989-08-01), Nakajima
patent: 4858143 (1989-08-01), Fournier
patent: 4918614 (1990-04-01), Modarres et al.
patent: 5295082 (1994-03-01), Chang et al.
patent: 5309370 (1994-05-01), Wong
Ho et al., "New Algorithms for the Rectilinear Steiner Tree Problem", IEEE Transactions on CAD, vol. 9, No. 2, Feb. 1990; pp. 185-193.
Hill et al., "Global Routing Considerations in a Cell Synthesis System", 1990 27th ACM/IEEE Design Automation Conference, pp. 312-316.
Kahng, "A Steiner Tree Construction for VLSI Routing", Neural Networks, 1991 IEEE Internat'l Conference, pp. 133-139.
Lewis et al., "Optimum Steiner Tree Generation", 2nd Great Lakes VLSI Sympos. 1992, pp. 207-212.
Makki et al., "The Steiner Tree Problem with Minimum Number of Vertices in Graphs," 2nd Great Lakes VLSI Symposium, 1992, pp. 204-206.
Matsumoto et al., "A New Efficient Algorithm for the Steiner Tree," 1990 IEEE Int'l Symposium on Circuits and Systems, pp. 2873-2874.
Matsumoto et al., "Two New Efficient Approximation Algorithms with ((Klogk) for the Steiner Tree Problem in Rectilinear Graphs," 1991 IEEE, pp. 1156-1159.
Sakai et al., "An Efficient Appox. Algorithm for the Steiner Tree Problem in Rectinear Graphs," 1989 IEEE Int'l Symposium, pp. 339-342.
Mehlhorn, Kurt; A Faster Approximation Algorithm for the Steiner Problem in Graphs; Information Processing Letters 27; Elsevier Science Publishers B.V. (North-Holland); 25 Mar. 1988, pp. 125-128.
M. Hanan, "On Steiner's Problem With Rectilinear Distance", J. Siam Applied Math, vol. 14, No. 2, Mar. 1966, pp. 255-265.
Ying-Fung Wu, Peter Widmayer, Martine D. F. Schlag, and C. K. Wong, "Rectlinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles", IEEE Transactions on Computers, vol. C-36, No. 3, Mar. 1987, pp. 321-331.
Charles Chiang and Majid Sarrafzadeh, "An Optimal Algorithm for Rectilinear Steiner Trees for Channels with Obstacles", International Journal of Circuit Theory and Applications, vol. 19, pp. 551-563 (1991).
Ding Cheng-Liang
Scepanovic Ranko
Garbowski Leigh Marie
LSI Logic Corporation
Teska Kevin J.
LandOfFree
Towards optical steiner tree routing in the presence of rectilin does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Towards optical steiner tree routing in the presence of rectilin, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards optical steiner tree routing in the presence of rectilin will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-244503