We consider the problem of placing a set of cells in a single row with a given horizontal ordering, minimizing the (weighted) bounding box netlength. We analyze the running time of an algorithm of Kahng, Tucker and Zelikovsky which solves this problem optimally. By using different data structures we are able to improve the worst-case running time in the unweighted case as well as in the presence of netweights.
['Ulrich Brenner', 'Jens Vygen']
Faster optimal single-row placement with fixed ordering