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