Key points are not available for this paper at this time.
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 n) algorithm. In this paper we solve the problem for undirected trees by an O (n^2. 2) algorithm.
Yossi Shiloach (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: