A fast and simple Steiner routing heuristic

This paper presents a simple yet efficient heuristic for rectilinear Steine r routing. The basic heuristic introduces a new edge into the existing tree for another, costlier edge such that the resulting graph remains a tree. T he simplicity of the heuristic led to an O(n(2)) implementation using basic data structures. Asymptotic time requirement of the heuristic can be furth er improved to O(n log n) using sophisticated data structures. Due to the g enerality of the heuristic different cost criteria can be applied to produc e routes with different properties. The heuristic has been successfully app lied to the problem of minimum-length Steiner routing and minimizing critic al-sink Elmore delay. (C) 1999 Elsevier Science B.V. All rights reserved.