Folding a stack of equal width components
V. Thanvantri, Sartaj K. Sahni · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1995
We consider two versions of the problem of folding a stack of equal width components. In both versions, when a stack is folded, a routing penalty is incurred at the fold. In one version, the height of the folded layout is given and we are to minimize width. In the other, the width of the folded layout is given and its height is to be minimized. We develop a normalization technique that permits the first version to be solved in linear time by a greedy algorithm. The second version can be solved efficiently using normalization and parametric search. Experimental results are presented.>