RMST Applet
Prim's Algorithm for Rectilinear Minimum Spanning Tree

This applet illustrates the construction of a Rectilinear Minimum Spanning Tree (RSMT) using Prim's Algorithm. A RMST connects all terminals together in a way that minimizes the overall distance of the connections in this tree. Prim's Algorithm operates incrementally on a partial tree starting with a single terminal - on each iteration, it adds an edge between the partial tree and the terminal that is closest to any terminal in the partial tree.

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.

There are several ways to edit the terminals shown in the animation:

  • Add a terminal by clicking at a location where no terminal exists.
  • Move a terminal by clicking and dragging to the desired location.
  • Delete a terminal by pressing the CONTROL key and clicking over an existing terminal.
Note that editing terminals will stop a running animation since the previously executed steps may no longer be valid.

Clicking the "AUTO" button places the applet in automatic mode, where the complete RMST is recalculated whenever the terminals are edited or moved.

About Rectilinear Mininimum Spanning Trees

Given a set of terminal points in a plane, a rectilinear minimum spanning tree is a set of edges which connects all the terminals with minimum rectilinear distance.  Rectilinear distance (also called "Manhattan Distance") is the sum of the horizontal and vertical distance between two points.  It is used instead of Euclidean distance in VLSI CAD applications because VLSI processes support only horizontal and vertical wires.

The RMST can be used as an estimate of the length of a net that connects together multiple terminals.

The RMST Problem is a special case of the Minimum Spanning Tree problem studied in Computer Science Algorithms textbooks in that the distances between the points imply a complete graph.

References

A. Kahng and I. Mandoiu, "GSRC Bookshelf RMST-Pack: Rectilinear Minimum Spanning Tree Algorithms", June 2001. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.

M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996.

Acknowledgement

This RMST code in this applet is derived from Joseph Ganley's "Interconnection Tree Applet", which can be found at http://ganley.org/software/tree.html





| CadApplets Home | RMST | Steiner Demo | Maze Router | Multilayer Maze Router | Placement | Annealing |

Last updated on May 23, 2006 by John A. Nestor