No abstract uploaded!

No abstract uploaded!

Submission of a manuscript implies: that the work described has not been published before (except in the form of an abstract or as part of a published lecture, review, or thesis); that it is not under consideration for publication elsewhere; that its publication has been approved by all coauthors, if any, as well as by the responsible authorities at the institute where the work has been carried out; that, if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher; and that the manuscript will not be published elsewhere in any language without the consent of the copyright holders.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double via insertion with wire bending (DVI/WB) in a post-routing stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The goal of DVI/WB is to primarily insert as many double vias as possible and to minimize the amount of layout perturbation as the secondary objective. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We propose algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. Moreover, we also propose a zero-one integer linear program (0-1 ILP) based approach to solve mWMIS. Experimental results show that

A few misprints occurred in the paper, due to technical typesetting problems. The editorial staff of Acta Mathematica apologizes for the mistake. The online version has been corrected. Corrections to the printed version are provided here.