Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00035
Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems
Vol. 5, no. 4, pp. 127, 2001. Regular paper.
Abstract Divideandconquer approximation algorithms for vertex ordering problems partition the vertex set of graphs, compute recursively an ordering of each part, and ``glue'' the orderings of the parts together. The computed ordering is specified by a decomposition tree that describes the recursive partitioning of the subproblems. At each internal node of the decomposition tree, there is a degree of freedom regarding the order in which the parts are glued together. Approximation algorithms that use this technique ignore these degrees of freedom, and prove that the cost of every ordering that agrees with the computed decomposition tree is within the range specified by the approximation factor. We address the question of whether an optimal ordering can be efficiently computed among the exponentially many orderings induced by a binary decomposition tree. We present a polynomial time algorithm for computing an optimal ordering induced by a binary balanced decomposition tree with respect to two problems: Minimum Linear Arrangement (${\rm MINLA}$) and Minimum Cutwidth (${\rm MINCW}$). For 1/3balanced decomposition trees of bounded degree graphs, the time complexity of our algorithm is $O( n^{2.2} )$, where $n$ denotes the number of vertices. Additionally, we present experimental evidence that computing an optimal orientation of a decomposition tree is useful in practice. It is shown, through an implementation for ${\rm MINLA}$, that optimal orientations of decomposition trees can produce arrangements of roughly the same quality as those produced by the best known heuristic, at a fraction of the running time.

Journal Supporters
