Patent ID: 7676781

Claim:
A computer implemented method for constructing a minimum spanning tree for at least placement or routing of an integrated circuit product, comprising: using a computer configured for performing: (a) identifying a point-pair that is a most recent point-pair added to the minimum spanning tree; (b) calculating a first nearest neighbor for a first point in the most recent point-pair, forming a first nearest neighbor point-pair using the first point and the first nearest neighbor, and adding the first nearest neighbor point-pair to a point-pair list and storing the point-pair list in a computer usable storage medium; (c) calculating a second nearest neighbor for a second point in the most recent point-pair, forming a second nearest neighbor point-pair using the second point and the second nearest neighbor, and adding the second nearest neighbor point-pair to the point-pair list; (d) determining a shortest point-pair from the point-pair list; (e) adding the shortest point-pair to the minimum spanning tree, in which the shortest point-pair becomes the most recent point-pair added to the minimum spanning tree; (f) repeating (a) through (e) until all relevant points on the integrated circuit product have been added to the minimum spanning tree, wherein each iteration of (a)-(e) does not examine all point-pairs for the integrated circuit product; and causing the integrated circuit product to be made by using at least information in the minimum spanning tree.