MARCO GSRC Calibrating Achievable Design: Bookshelf

Rectilinear Steiner Minimum Tree Slot

Work in progress: last updated Thu Apr 12 2001

(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 heuristics (BOI and BI1S) 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 and BOI heuristics come on the average within .5% of the RSMT.

Contents

0.  Ion Mandoiu's comparisons of fast RMST algorithms 
I.  Joe Ganley's Steiner Tree Page 
II.  Dr. Patrick Madden's BOI Code  
III. Dr. Gabriel Robins' BI1S Code  
IV. Dr. Lou Scheffer's O(n log n) RMST