Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-06-27
2006-06-27
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
07069531
ABSTRACT:
Some embodiments of the invention provide a method for identifying a path between a set of source states and a set of target states in a space with more than two dimensions. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. At least some of the states are non-zero dimensional states. For instance, in some embodiments, the space is a graph that includes points, lines, and surfaces. The method specifies at least one path that starts from one state. It then iteratively specifies new paths by expanding previously specified paths to other states in the space until identifying a path that connects the source and target states. At least one of the expansions of a previously specified path includes an expansion in more than two dimensions of the space.
REFERENCES:
patent: 4777606 (1988-10-01), Fournier
patent: 4858143 (1989-08-01), Fournier
patent: 5224057 (1993-06-01), Igarashi et al.
patent: 5550748 (1996-08-01), Xiong
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5673201 (1997-09-01), Malm et al.
patent: 5717600 (1998-02-01), Ishizuka
patent: 5757089 (1998-05-01), Ishizuka
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 5811863 (1998-09-01), Rostoker et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5856927 (1999-01-01), Greidinger et al.
patent: 5877091 (1999-03-01), Kawakami
patent: 5880969 (1999-03-01), Hama et al.
patent: 5889329 (1999-03-01), Rostoker et al.
patent: 5889677 (1999-03-01), Yasuda et al.
patent: 5898597 (1999-04-01), Scepanovic et al.
patent: 5971596 (1999-10-01), Nishikawa
patent: 5973376 (1999-10-01), Rostoker et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6006024 (1999-12-01), Guruswamy et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6110222 (2000-08-01), Minami et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6154873 (2000-11-01), Takahashi
patent: 6154874 (2000-11-01), Scepanovic et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6219823 (2001-04-01), Hama et al.
patent: 6226560 (2001-05-01), Hama et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6247167 (2001-06-01), Raspopovic et al.
patent: 6247853 (2001-06-01), Papadopoulou et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6259988 (2001-07-01), Galkowski et al.
patent: 6262487 (2001-07-01), Igarashi et al.
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6292929 (2001-09-01), Scepanovic et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6327693 (2001-12-01), Cheng et al.
patent: 6327694 (2001-12-01), Kanazawa
patent: 6330707 (2001-12-01), Shinomiya et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6407434 (2002-06-01), Rostoker et al.
patent: 6412102 (2002-06-01), Andreev et al.
patent: 6415427 (2002-07-01), Nitta et al.
patent: 6434730 (2002-08-01), Ito et al.
patent: 6436804 (2002-08-01), Igarashi et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
patent: 6490713 (2002-12-01), Matsumoto
patent: 6499132 (2002-12-01), Morley et al.
patent: 6505331 (2003-01-01), Bracha et al.
patent: 6601227 (2003-07-01), Trimberger
patent: 6609237 (2003-08-01), Hamawaki et al.
patent: 6645842 (2003-11-01), Igarashi et al.
patent: 6656644 (2003-12-01), Hasegawa et al.
patent: 6665852 (2003-12-01), Xing et al.
patent: 6851101 (2005-02-01), Kong et al.
patent: 2001/0003843 (2001-06-01), Scepanovic et al.
patent: 2001/0038612 (2001-11-01), Vaughn et al.
patent: 2002/0043988 (2002-04-01), Or-Bach et al.
patent: 2002/0100009 (2002-07-01), Xing et al.
patent: 2002/0104061 (2002-08-01), Xing et al.
patent: 2002/0107711 (2002-08-01), Xing et al.
patent: 2002/0182844 (2002-12-01), Igarashi et al.
patent: 2003/0005399 (2003-01-01), Igarashi et al.
patent: 2003/0009737 (2003-01-01), Xing
patent: 2003/0014725 (2003-01-01), Sato et al.
patent: 2003/0025205 (2003-02-01), Shively
patent: 2003/0121017 (2003-06-01), Andreev et al.
patent: 2003/0188281 (2003-10-01), Xing
patent: 2004/0044979 (2004-03-01), Aji et al.
patent: 2004/0088670 (2004-05-01), Stevens et al.
patent: 02-262354 (1990-10-01), None
patent: 11-296560 (1999-10-01), None
N. Chang et al., Optimal Controlled Flooding Search in a Large Wireless Network, Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pp. 229-237, Apr. 2005.
Chen, H.F. et al., A Faster Algorithm for Rubber-Band Equivalent Transformation for Planar VLSI Layouts, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 2, Feb. 1996, pp. 217-227.
Dayan, T. et al., Layer Assignment for Rubber Band Routing, UCSC-CRI-93-04, Jan. 20, 1993.
Dayan, T., Rubber-Band Based Topological Router, A Dissertation, UC Santa Cruz, Jun. 1997.
Hama, T. et al., Curvilinear Detailed Routing Algorithm and its Extension to Wire-Spreading and Wire-Fattening.
Hama, T. et al., Topological Routing Path Search Algorithm with Incremental Routability Test, IEEE Transactions on Computer-Aided design of Integrated Circuits and Systems, vol. 18, No. 2, Feb. 1999, pp. 142-150.
Kobayashi, K. et al., A New Interactive Analog Layout Methodology based on Rubber-Band Routing, UCSC-CRL-96-12, Jun. 13, 1996.
Lim, A. et al, A Fast Algorithm To Test Planar Topological Routability, Technical Report 94-012, pp. 1-16.
Lu, Y., Dynamic Constrained Delaunay Triangulation and Application to Multichip Module Layout, A Thesis for Master of Science, UC Santa Cruz, Dec. 1991.
Maley, F.M., Testing Homotopic Routability Under Polygonal Wiring Rules, Algorithmica 1996, 15: 1-16.
Morton, P. B. et al., An Efficient Sequential Quadratic Programming Formulation of Optimal Wire Spacing for Cross-Talk Noise Avoidance Routing, UCSC-CRL-99-05, Mar. 10, 1999.
Staepelaere, D. et al., Geometric Transformations for a Rubber-Band Sketch, A Thesis for a Master of Science in Computer Engineering, UCSC, Sep. 1992.
Staepelaere, D. et al., Surf: A Rubber-Band Routing System for Multichip Modules, pp. 18-26, 1993.
Su, J. et al., Post-Route Optimization for Improved Yield Using Rubber-Band Wiring Model, 1997 International Conference on Computer-Aided design, pp. 700-706, Nov. 1997.
Wei-Ming Dai, W. et al., Routability of a Rubber-Band Sketch. 28thACM-IEEE Design Automation Conference, 1991, pp. 45-65.
Xing, Z. et al., A Minimum Cost Path Search Algorithm Through Tile Obstacles, slide presentation.
Xing, Z. et al., Shortest Path Search Using Ties and Piecewise Linear Cost Propagation, IEEE, 2002, pp. 145-158.
XU, A More Efficient Distance Vector Routing Algorithm, UCSC-CRL-96-18, Mar. 1997.
Yu, M.-F. et al., Fast and Incremental Routability Check of a Topological Routing Using a Cut-Based Encoding, UCSC-CRL-97-07, Apr. 14, 1997.
Yu, M.-F. et al, Interchangeable Pin Routing with Application to Package Layout, UCSC-CRL-96-10, Apr. 25, 1996.
Yu, M.-F. et al., Pin Assignment and Routing on a Single-Layer Pin Grid Array, UCSC-CRL-95-15, Feb. 24, 1995.
Yu, M.-F. et al., Planar Interchangeable 2-Terminal Routing, UCSC-CRL-95-49, Oct. 19, 1995.
Yu, M.-F. et al., Single-Layer Fanout Routing and Routability Analysis for Ball Grid Arrays, UCSC-CRL-95-18, Apr. 25, 1995.
Ahuja, R. et al., Faster Algorithms for the Shortest Path Problem, Journal of the Association for Computing Machinery, vol. 37, No. 2, Apr. 1990, pp. 213-223.
Bagga, J. et al., Internal, External, and Mixed Visibility Edges of Polygons.
Berger, B. et al., Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, Journal of the Association for Coomputing Machinery, pp. 500-542, Mar. 1995.
Chen et al., Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing, May 1994, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions vol. 13 Issues, pp. 603-609.
Cheng, K., Steiner Problem in Octilinear Routing Model, A Thesis
Caldwell Andrew
Teig Steven
Cadence Design Systems Inc.
Stattler Johansen & Adeli LLP
Thompson A. M.
LandOfFree
Method and apparatus for identifying a path between source... 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 identifying a path between source..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for identifying a path between source... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3631184