Abstract
The objective of the invention is to provide a method for post-routing redundant via insertion. The method is to construct a conflict graph from a post-routing design first, to find a maximal independent set (MIS) of the conflict graph, and to replace a single via with a double via for each vertex in the maximal independent set. Furthermore, since redundant vias can be classified into on-track and off-track ones and since on-track ones have better electrical properties, the invention also presents two methods to increase the amount of on-track redundant vias while a redundant via insertion solution is given.