A minimum cost path search algorithm through tile obstacles

ABSTRACT

In this paper, based on tile connection graph, we propose an efficient minimum cost path search algorithm through tile obstacles. This search algorithm is faster than previous graph based algorithm and unlike previous tile based algorithms, this algorithm finds the minimum cost path.

REFERENCES

• 1: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 2: L. Chua, C. Desoer, and E Kuh, Linear and Nonlinear Circuits, McGraw-Hill, Inc, 1987.
• 3: Jeremy Dion and Louis M. Monier, "Contour: A Tile-based Gridless Router," Western Research Laboratory Research Report 95/3, Palo Alto, California.
• 4: Margarino, A. Romano, A. De Gloria, F. Curatelli, and P. Antognetti, "A Tile-Expansion Router," IEEE Transactions on Computer-Aided Design CAD-6(4): 507-517, July, 1987.
• 5: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 6: John K. Ousterhout, "Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools." IEEE Transactions on Computer-Aided Design, Vol. CAD-3, NO. 1, pp. 87-100, January 1984.
• 7: Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
• 8: Tsai, S. Chen, and W. Feng, "An H-V Alternating Router," IEEE Transactions on Computer-Aided Design 11(8):976- 991, August, 1992.
• 9: Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]
• 10: S. Zheng, J Lim, and S. Iyengar, "Finding Obstacle-Avoiding Shortest Paths Using Implicit Connection Graphs," IEEE Transactions on Computer-Aided Design, Vol. 15, No. 1, January 1996.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design, Theory

Keywords:
VLSI routing, shortest path search