A Multi-centrality Heuristic for the Bandwidth Reduction Problem

The Bandwidth Minimization Problem for Sparse Matrices is a well-known NP-Hard problem critical in numerous significant scientific applications. The Cuthill-McKee algorithm, a heuristic based on degree centrality for minimizing bandwidth, is a common solution approach. One can integrate other centrality measures into the Cuthill-McKee method or similar algorithms. This work explores the impact of utilizing these diverse centrality measures on the performance of the Cuthill-McKee heuristic. It introduces a novel multi-centrality constructive algorithm designed as an alternative for practical applications emphasizing efficient execution for large linear systems. The results demonstrate clear advantages of considering multiple centrality measures over solely degree centrality. This approach notably enhances the heuristic’s effectiveness, offering significant improvements in solving complex bandwidth minimization problems.