ON THE MINCUT BIPARTITE ARRANGEMENT PROBLEM.

The placement problem that minimizes the channel density in the standard cell (polycell) layout is considered. This problem is formalized as a min-cut arrangement problem for a given bipartite graph G equals (A, B, E), where the vertices of A and B are placed on two different rows. It is shown that this problem is NP-hard even when the positions of the vertices in A are fixed. In this restricted version, an O(nlog n) optimal algorithm is given for three-regular bipartite graphs. Also given are a three-approximation algorithm for regular bipartite graphs, i. e. , an algorithm whose answer is guaranteed not to be more than a factor of three of the optimal solution, and a (d plus 1)-approximation algorithm for bipartite graphs with degree at most d.