FLOATING STEINER TREES

We study the reproducing placement problem, which finds application in layout-driven logic synthesis. In each phase, a module (or gate) is d ecomposed into two (or more) simpler modules. The goal is to find a '' good'' placement in each phase. The problem, being iterative in nature , requires an iterative algorithm. In solving the RPP, we introduce th e notion of minimum floating Steiner trees (MFST). We employ an MFST a lgorithm as a central step in solving the RPP. A Hanan-like theorem is established for the MFST problem, and two approximation algorithms ar e proposed. Experiments on commonly employed benchmarks verify the eff ectiveness of the proposed technique.