The optimal linear arrangement problem: Algorithms and approximation.

摘要

Given a finite graph {dollar}G = (V, E){dollar} of order n, the optimal linear arrangement problem (OLA) seeks a vertex labeling {dollar}f{lcub}:{rcub}Vto{lcub}1,2,...,n{rcub}{dollar} such that {dollar}sumlimitssb{lcub}(u,v)in E{rcub}vert f(u) - f(nu)vert{dollar} is minimum over all such labelings. The problem is hard in general but is known to be solved in certain special cases among which are paths, cycles, trees, and outerplanar graphs. After a survey of what is known about OLA as well as about variations such as minimum bandwidth and other "p-sum" problems, this thesis describes new algorithms for OLA on other graph classes. Several bounds on the cost of arrangements as well as a new algorithm for calculating one of these bounds for recursively constructed graphs are examined. Various heuristic procedures for OLA are also discussed, both from the literature as well as new ones resulting from this research. The thesis concludes with some directions for further research.