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@cs.ucla.edu
mandoiu@cs.ucsd.edu
