MARCO GSRC Calibrating Achievable Design: Bookshelf

Rectilinear Steiner Minimum Tree Slot

Work in progress: last updated Wed Feb 19, 2003

(see other slots)

Joe Ganley, Patrick Madden, Gabriel Robins and Ion Mandoiu



This slot is focused on the Rectilinear Steiner Minimum Tree (RSMT) problem:

Problem

Given a set P of n points, find a set S of Steiner points such that the Minimum Spanning Tree (MST) over P + S has minimum cost.

The RSMT problem is NP-hard. This page presents an exact algorithm (GeoSteiner), two quadratic heuristics (BOI and BI1S), a O(nlog2n) heuristic (batched greedy), and a O(n log n) Rectilinear Minimum Spanning Tree (RMST) code. The RMST is never more than 50% longer than RSMT, and on the average comes within 12% of the RSMT. The BI1S, BOI, and batched greedy heuristics come on the average within 0.5-0.7% of the optimum RSMT.

Contents

I.  The GeoSteiner algorithm 
II.  Dr. Patrick Madden's BOI Code  
III. Dr. Gabriel Robins' BI1S Code  
IV. Highly scalable rectilinear and octilinear Steiner Tree code based on batched triple contraction 
V.  Dr. Lou Scheffer's O(n log n) RMST  
VI. Ion Mandoiu's comparisons of fast RMST algorithms 
VII.  Joe Ganley's Steiner Tree Page 
VII.  FLUTE: Fast Lookup Table Based Technique for Wirelength Estimation and RSMT Construction by Chris Chu