Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2008-07-08
2008-07-08
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
10803516
ABSTRACT:
The present invention provides a new approach and algorithm to optimize various design parameters in global routing. According to an exemplary aspect of the present invention, marked trees are first preprocessed. For every vertex incident to leaves, one may go through the list of its leaves, and if two leaves have the same mark one may leave only one of them. After that whether homeomorphism exists may be determined. The reason behind selecting such homeomorphic pairs is as follows: adding or removing a vertex of degree 2 as well as adding or removing a new leaf (variable) does not significantly modify routing (in this case all routing transformations are in essence splitting and merging routing trees). After the selection of applicable transformations, one may apply them to optimize design parameters. This may be achieved by assigning the same coordinates to nodes of degree !=2 of homeomorphic trees, which means that one may assign the coordinates of corresponding nodes to “essential” nodes and then insert or remove nodes of degree 2.
REFERENCES:
patent: 7152031 (2006-12-01), Jensen et al.
Maciej M. Syslo, “On the Fundamental Cycle Set Graph,” IEEE, Mar. 1982, pp. 136-138.
David S. Johnson, “The NP-Completeness: An Ongoing Guide,” Published in J. ALGORHTMS 2, 393-405 (1981), pp. 1-12.
Gunter Rote, “Binary trees having a given number of nodes with 0, 1 and 2 children,” Institute fur Mathematik, Technische University Graz, Austria, http://www.tu-graz.ac.at/rote, Aug. 1997, pp. 1-6.
David Nassimi, “A Parallel MSF Algorithm for Planar Graphs on a Mesh and Applications to Image Processing,” IEEE, 1993, pp. 205-211.
Chen et al., “Meet and Merge: Approximation Algorithms for Confluent Flows,” ACM, Jun. 9-11, 2003, pp. 373-382.
Goodman et al., “Advances on teh Hamiltonian Completion Problem,” Journal of the Association for Computing Machinery, vol. 22, No. 3, Jul. 1975, pp. 352-360.
Andrew Vince, “Separation Index of a Graph,” 2002 wiley periodicals, Inc., 2002, pp. 53-61.
Keselman et al., “Maximum Agreement Subtree in a Set of Evolutionary Trees—Metrics and Efficient Algorithms,” IEEE, 1994, pp. 758-769.
Galatenko Alexei V.
Gasanov Elyar E.
Zolotykh Andrej A.
LSI Corporation
Siek Vuthe
Suiter Swantz PC LLO
LandOfFree
Method and apparatus for performing logical transformations... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing logical transformations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing logical transformations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3929884