Method and apparatus for performing logical transformations...

Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C716S030000

Reexamination Certificate

active

07398486

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-2770387

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.