A branch-and-bound algorithm for the minimum cut linear arrangement problem

摘要

Given an edge-weighted graph G of order n, the minimum cut linear arrangement problem (MCLAP) asks to find a one-to-one map from the vertices of G to integers from 1 to n such that the largest of the cut values c1, . . ., cn-1 is minimized, where ci, i ε {1, . . ., n - 1}, is the total weight of the edges connecting vertices mapped to integers 1 through i with vertices mapped to integers i + 1 through n. In this paper, we present a branch-and-bound algorithm for solving this problem. A salient feature of the algorithm is that it employs a dominance test which allows reducing the redundancy in the enumeration process drastically. The test is based on the use of a tabu search procedure developed to solve the MCLAP.We report computational results for both the unweighted and weighted graphs. In particular, we focus on calculating the cutwidth of some well-known graphs from the literature.