Hierarchical global routing through structured Steiner trees


The Steiner problem in a hierarchical graph model, called a structured graph, is defined for a specific application to the hierarchical global routing problem. Properties of minimum-cost Steiner trees in structured graphs are investigated. A top-down solution to the Steiner problem in structured graphs is defined, and an algorithm is given in order to compute such a solution (or an approximation) on the basis of existing exact or heuristic algorithms for solving the Steiner problem on graphs

Circuits and Systems, 1989., IEEE International Symposium on