Answers are grounded in this paper and cite their sources.
Algorithmic evaluation demonstrates superior solution quality and 800-fold speedup for the small boundary heuristic across 26 large-scale graphs, indicating practical scalability for linear graph...
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.
No takes yet. Share an insight, caveat, or question.
Oliveira et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: