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 c
1,…,c
n−1 is minimized, where c
i
, 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.
