Performance Oriented Rectilinear Steiner Trees

We formulate the performance oriented minimum rectilinear Steiner tree problem (POMRST) which is useful in the case of net connection high performance circuits. Since the POMRST problem is NP-hard, we provide an effective heuristic for it. When we apply our POMRST heuristic to solve the rectilinear Steiner tree problem, our experimental results compare favorably with the existing techniques cited in [11]. In the context of the POMRST problem, our experimental results indicate that a small increase in the total interconnection length can greatly enhance the circuit performance. A related but less general problem has been addressed in [1].