Small boundary: a family of linear-time greedy heuristics for the minimum linear arrangement problem
TL;DR
Small boundary (SB(k)), a family of linear-time greedy heuristics that guide vertex labeling through a prioritization scheme based on the structure of labeled and k levels of unlabeled vertex neighborhoods, is introduced.
Abstract
This paper addresses the minimum linear arrangement problem, a classical graph layout problem in which the objective is to minimize the sum of absolute differences between the labels assigned to adjacent vertices in undirected graphs. The paper introduces small boundary (SB(k)), a family of linear-time greedy heuristics that guide vertex labeling through a prioritization scheme based on the structure of labeled and k levels of unlabeled vertex neighborhoods. An extensive experimental evaluation on 26 large-scale real-world graphs demonstrates that the proposed heuristic with k=2 consistently outperforms 19 established low-cost graph-theoretic reordering algorithms, including the leading constructive method used within a high-performing metaheuristic algorithm for the problem. Additionally, the SB(2) heuristic outperforms this high-performing metaheuristic algorithm while requiring up to 800 times less computational effort. The paper further shows that integrating SB(2) as the initialization procedure within this metaheuristic yields improved solution quality, highlighting its effectiveness as both a standalone heuristic and a high-quality initializer. Overall, the proposed approach provides a fast, scalable, and practical solution for tackling MinLA on large-scale graphs.