As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of VLSI circuits. In this paper we focus on one reliability issue-jumper insertion in routing trees for avoiding/fixing antenna effect violations at the routing/post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an  O ( V  lg  V )-time exact jumper insertion algorithm that uses the optimum number of jumpers to avoid/fix the antenna violations in a routing tree with  V  vertices. Experimental results show the superior effectiveness and efficiency of our algorithm.
['Bor-Yiing Su', 'Yao-Wen Chang']
An exact jumper insertion algorithm for antenna effect avoidance/fixing