MARCO GSRC Calibrating Achievable Design: Bookshelf

RMST-Pack: Rectilinear Minimum Spanning Tree Algorithms

Andrew B. Kahng Ion Mandoiu

Last updated: Mon Jun 4, 2001

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:

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

abk@ucsd.edu
mandoiu@cs.ucsd.edu