8
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Using structured steiner trees for hierarchical global routing

, &
Pages 169-192 | Received 04 Oct 1990, Published online: 19 Mar 2007
 

Abstract

The Steiner problem in a hierarchical graph model, the structured graph, is defined. The problem finds applications to hierarchical global routing. Properties of minimum-cost Steiner trees in structured graphs are investigated. A “top-down” approximate solution to the Steiner problem in structured graphs, called a top-down Steiner tree, is defined, and an algorithm is given to compute such solution. The top-down Steiner tree provides also an approximate solution to the Steiner problem in graphs admitting a structured representation. The properties of such solution are discussed and some experimental results on the quality of the approximation are presented. A reduction in time complexity is demonstrated with respect to both exact and heuristic algorithms applied to such graphs.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.