Su, Bor-YiingBor-YiingSuYAO-WEN CHANG2020-06-162020-06-1620050738100Xhttps://scholars.lib.ntu.edu.tw/handle/123456789/501962https://www.scopus.com/inward/record.uri?eid=2-s2.0-27944508730&doi=10.1145%2f1065579.1065664&partnerID=40&md5=9db003ddbb73795e9e4fba137ccced12As 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. Copyright 2005 ACM.Antenna Effect; Jumper InsertionAntenna arrays; Problem solving; Product design; Reliability; Routers; Trees (mathematics); VLSI circuits; Antenna effects; Jumper insertion; Optimal substructures; Algorithmsconference paper10.1145/1065579.10656642-s2.0-27944508730https://doi.org/10.1145/1065579.1065664