TCS Journal 2001 Journal Article
Wire segmenting for buffer insertion based on RSTP-MSP
- Bing Lu
- Jun Gu
- Xiaodong Hu
- Eugene Shragowitz
This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple smaller segments and minimize the number of the buffer insertion points (Steiner points) which are only located at the end of each segment. We show that (a) the Steiner ratio is 1 3, that is, the rectilinear minimum spanning tree yields a polynomial-time approximation with a performance ratio exactly 3; (b) there exists a polynomial-time approximation with a performance ratio 2.