A fast and simple Steiner routing heuristic

This paper presents a simple yet efficient heuristic for rectilinear Steiner routing. The basic heuristic introduces a new edge into the existing tree for another, costlier edge such that the resulting graph remains a tree. The simplicity of the heuristic led to an O(n²) implementation using basic data structures. Asymptotic time requirement of the heuristic can be further improved to O(n log n) using sophisticated data structures. Due to the generality of the heuristic different cost criteria can be applied to produce routes with different properties. The heuristic has been successfully applied to the problem of minimum-length Steiner routing and minimizing critical-sink Elmore delay.