MARCO GSRC Calibrating Achievable Design: Bookshelf

FastSteiner: Highly Scalable Rectilinear and Octilinear Minimum Steiner Tree Algorithms

Last updated: Fri Sep 16, 2005

I. Introduction

This page gives a practical O(nlog²n) batched greedy triple contraction heuristic for computing near-optimal rectilinear and octilinear Steiner trees.

II. Experimental Comparison

See the paper below for solution quality and runtime comparison of the batched greedy algorithm with the Guibas-Stolfi MST code, Rohe's Prim-based heuristic, the edge-based heuristic of Borah, Owens, and Irwin, and GeoSteiner.

III. Source code

NEW! The source code below is an updated version contributed by Jarrod Alexander Roy from the University of Michigan. This version removes a bug that caused the original code to crash for inputs containing duplicated points or for which an added Steiner point duplicates an existing terminal. For a full list of modification see the README file below.

IV. Benchmarks

iccad01_testcases.tar.gz

V. References

A.B. Kahng, I.I. Mandoiu, and A. Zelikovsky, Highly scalable algorithms for rectilinear and octilinear Steiner trees, Proc. 2003 Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 827-833.

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