Some Results And Problems On Minimum Linear Arrangement Problem

The minimum linear arrangement problem (shortly for MinLA) is a particular class of combinational optimization problem. For an undirected, weighted graph G=(V, E) of order n, nonnegative edge weights cij≥0for ij∈E, it’s goal is to find a bijective function Ï€:Vâ†'{1,2,…,n} so that the sum of the resulting edge length LA(Ï€,G)=Σij∈ECij|Ï€(i)-Ï€(j)|is minimized. The problem is known to be NP-Hard in general, but polynomial for some particular classes of graphs. In recent years, some progress occurred; we review the problem on complexity and the upper and lower bounds. Then, we examine the following notion. Give some G, is there a spanning tree of G having an optimal labeling that is also optimal for G? We specify some graph classes, which always exhibit these critical spanning trees. The road map of this paper is as follows:first of all, in chapter1, we formally define the minimum linear arrangement problem, state some basic properties and an overview with motivations and applications for MinLA is surveyed. Chapter2presents the complexity of MinLA. Afterwards, in chapter3, we present some methods to obtain upper and lower bounds of MinLA. Chapter4considers the critical spanning tree of MinLA, we find some graphs satisfy the condition. Finally, in chapter5we close the paper with some open problems.