MARCO GSRC Calibrating Achievable Design: Bookshelf
RMST-Pack: Rectilinear Minimum Spanning Tree Algorithms
I. Introduction
The rectilinear minimum spanning tree (RMST) problem is a fundamental problem in VLSI CAD. Given n terminals in the plane, the RMST problem asks for a minimum length tree spanning the terminals, where edge lengths are measured in the L1 (Manhattan) metric. This software package bundles implementations of three algorithms for computing RMSTs: - An O(n^2) time implementation of Prim's (also called priority first) algorithm for computing the minimum spanning tree (MST) of the implicitly represented complete graph defined by terminals.
- An O(n logn) time algorithm that first computes octant nearest neighbors for each terminal using the elegant divide-and-conquer algorithm of Guibas and Stolfi, then finds the MST of this graph using a binary-heap implementation of Prim's algorithm.
- An RMST code contributed by Dr. Lou Scheffer combining Prim's algorithm with on-the-fly computation of the octant nearest neighbors via quad-tree based rectangular range searches.
II. Experimental Comparison
Below are average running times (CPU seconds on an 195MHz SGI Origin 2000, excluding I/O and memory allocation) over 10 instances of each size. Minimum in each row is shown in red. #terminals O(n^2) Prim Scheffer Guibas-Stolfi
-------------------------------------------------
5 0.000006 0.000400 0.000053
10 0.000024 0.000685 0.000138
50 0.000567 0.003601 0.001118
100 0.002269 0.007959 0.002613
500 0.055323 0.051744 0.017536
1000 0.223079 0.118234 0.038819
5000 5.774400 0.889230 0.243520
10000 23.641100 2.477000 0.531860
50000 N/A 22.685750 3.461500
100000 N/A 75.654200 9.253000
500000 N/A 486.621200 91.634800
-------------------------------------------------
III. Source code
IV. References- L.J. Guibas and J. Stolfi, On computing all northeast nearest neighbors in the L1 metric, Information Processing Letters, 17 (1983), pp. 219--223.
- R.C. Prim, Shortest interconnection network and some generalizations, Bell System Tech. J., 36 (1967), pp. 1389--1401.
abk@ucsd.edu
mandoiu@cs.ucsd.edu
