Patent ID: 8635576

Claim:
A non-transitory computer-accessible storage medium having program instructions stored therein that, in response to execution by a computer system, causes the computer system to perform operations comprising: receiving a plurality of terminal nodes, each corresponding to a vertex of a signal route of an integrated circuit; receiving one or more pre-routed edges, each corresponding to a pre-determined connection between a given terminal node of the plurality of terminal nodes and another terminal node of the plurality of terminal nodes; determining one or more candidate connections between a particular point on each pre-routed edge and any remaining terminal nodes of the plurality of terminal nodes; determining a connection distance for each of the one or more candidate connections; storing in a respective one of a plurality of node heaps, each candidate connection having a connection distance that is less than a respective one of a plurality of pre-determined threshold distances, wherein each node heap corresponds to a respective node of the remaining terminal nodes, and wherein each pre-determined threshold distance corresponds to a respective node of the remaining terminal nodes; forming a minimum Steiner tree, wherein the minimum Steiner tree includes a minimum candidate connection from each node heap of the plurality of node heaps.