A Variable Neighbourhood Search approach to the Cutwidth Minimization Problem

Abstract

The Cutwidth Minimization Problem, also known as the Minimum Cut Linear Arrangement consists of finding an arrangement of the vertices of a graph on a line, in such a way that the maximum number of edges between each pair of consecutive vertices is minimized. This problem has practical applications in VLSI Design, Network Migration and Graph Drawing, among others. In this paper we propose several heuristics based on the Variable Neighbourhood Search methodology to tackle the problem and we compare them with other state-of-the-art methods.