Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Abstract

The min-cut linear arrangement problem is one of several one-dimensional layout problems for undirected graphs that may be of relevance to VSLI design. This paper gives a polynomial time algorithm that finds a min-cut linear arrangement of trees whose cost is within a factor of 2 of optimal. For complete m-ary trees a linear time algorithm is given that finds an optimum min-cut linear arrangement.