Patent ID: 7302662

Claim:
A method for post-routing via insertion comprising: forming a conflict graph by simultaneously constructing edge and vertex sets from a post-routing design, wherein each vertex of a vertex set corresponds to a feasible double via such that if two vertices of the vertex set are endpoints of an edge, then either an existence of corresponding double vias violates design rules or corresponding two double vias come from a same single via, the step of forming comprising: establishing a vertex comparison set by extending bounding boxes of feasible double vias in which said vertex comparison set is empty at a beginning; sorting all single vias by x-coordinates thereof in non-decreasing order and according to a sorted order; deleting each bounding box from the vertex comparison set if a distance between the bounding box and the single via exceeds a threshold value; identifying feasible double vias for each single via; adding vertices corresponding to the feasible double vias to said conflict graph; adding an edge between a vertex corresponding to a feasible double via and a vertex corresponding to an element of said vertex comparison set that conflicts with the feasible double via; adding a bounding box to the vertex comparison set for each feasible double via identified in the step of identifying feasible double vias; adding an edge between each pair of the vertices corresponding to the feasible double vias identified in the step of identifying feasible double vias; and repeating the above steps until all single vias are processed in which the step of deleting each boundary box is skipped if a single via in verification is of a same coordinate as a single via that has been verified; obtaining a maximal independent set solution of said conflict graph in which vertices in the maximal independent set have no edges between each pair of the vertices; and replacing the single vias with double vias corresponding to the vertices in the maximal independent set.