BOI Steinerg Tree Demonstration Applet - John A. Nestor

BOI Steiner Applet Borah-Owens-Irwin Heuristic for Steiner Trees This applet illustrates the Borah-Owens-Irwin algorithm for constructing a Steiner Tree. The algorithm starts with a Rectilinear Minimum Spanning Tree (RSMT) and searches for node/edge pairs such that connecting the node to the edge creates a new Steiner Point and creates a cycle in the tree. The longest edge in the cycle is then deleted, creating a new tree that improves the overall cost of the tree. Node/edge pairs are examined and ranked by potential gain and applied in that order. To Use the Applet This applet creates a small number of terminals at random locations. Use the "VCR" controls to start, pause, single-step or stop the animation. References M. Borah, R. Owens, and M. J. Irwin, "An Edge-Based Heuristic for Steiner Routing", IEEE Trans. CAD, Vol 13, No. 12, pp 1563-1568. December, 1994. J. Ganley, P. Madden, G. Robins, and I. Mandoiu, "GSRC Bookshelf Rectilinear Steiner Minimum Tree Slot", February 2003. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/. M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996. Acknowledgement This RMST code in this applet is derived from Patrick Madden's Steiner Tree code which can be found at the href="http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/" target="_new">http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/.

| CadApplets Home | RMST | Steiner Demo | Maze Router | Multilayer Maze Router | Placement | Annealing |
Last updated on May 23, 2006 by John A. Nestor