An experimental study of the minimum linear colouring arrangement problem
Montserrat Brufau Vidal · RECERCAT (Consorci de Serveis Universitaris de Catalunya) · 2017
The Minimum Linear Colouring Arrangement problem (MinLCA) is a variation from the Minimum Linear Arrangement problem (MinLA) and the Colouring problem. The objective of our problem is finding the best proper colouring of a graph for which the sum of the induced distances between two adjacent vertices is the minimum. In this project, we undertake the task of broadening the previous studies for the MinLCA problem. The main goal is developing some exact algorithms based on backtracking and some heuristic algorithms based on a maximal independent set approach and testing them with different instances of graph families. As a secondary goal we are interested in providing theoretical results for particular graphs. The results will be made available in a simple, open-access benchmarking platform.