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.
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/. |