A Minimum Linear Arrangement Algorithm for Undirected Trees

Abstract

The minimum linear arrangement problem is a special case of more general placement problems which are discussed in Hanan and Kurtzberg [5] and might occur in solving wiring problems as well as many other placement problems. It is also a special case of the quadratic assignment problem [5] and has a lot in common with job sequencing problems (Adolphson and Hu [1, § 4]). The minimum linear arrangement problem for general undirected graphs is $NP$ complete as shown in Garey et al. [2]. The corresponding problem for acyclic directed graphs is also $NP$ complete (Evan and Shiloach [4]). D. Adolphson and T. C. Hu [1] solved the problem for rooted trees by an $O(n\log n)$ algorithm. In this paper we solve the problem for undirected trees by an $O(n^{2.2} )$ algorithm.