Patent ID: 8601425

Claim:
A computer implemented method for solving a congestion problem in an integrated circuit (IC) design, the method comprising: selecting, using an application executing using a processor and a memory in a data processing system, a congested g-edge from a set of congested g-edges; selecting a set of congesting nets, wherein the set of congesting nets causes congestion in the selected congested g-edges by crossing the selected congested g-edge; populating a vacancy data structure corresponding to the selected congested g-edge, wherein the vacancy data structure stores available track information of a set of g-edges and wherein the information is indexed by a distance between the selected congested g-edge and g-edge in the set of g-edges; selecting a subset of the set of the congesting nets; and rerouting the subset of the set of the congesting nets to a candidate g-edge identified in the vacancy data structure.