Minimal Steiner Trees in X Architecture with Obstacles

摘要

The Steiner minimal tree problem in X architecture is the problem of connecting a set terminals Z using orthogonal, diagonal, and vertical edges with minimum length. This problem has many applications, especially for the routing of VLSI circuits. This paper proposes an obstacle-avoiding heuristic for this problem based on the Areibi's concepts and Prim's minimal spanning tree algorithm, and the Steiner ratio of this approach is 1.25. The space and time complexities are O(N~2) and O(N~2 +p~3N) respectively, where N and p are the numbers of free and terminal vertices (p ≤ N).