.png){kind=icon}
返回
Efficient iterated greedy for the two-dimensional bandwidth minimization problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2022.09.004.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Graph layout problems are a family of combinatorial optimization problems that consist of finding an em-bedding of the vertices of an input graph into a host graph such that an objective function is optimized. Within this family of problems falls the so-called Two-Dimensional Bandwidth Minimization Problem (2DBMP). The 2DBMP aims to minimize the maximum distance between each pair of adjacent vertices of the input graph when it is embedded into a grid host graph. In this paper, we present an efficient heuris-tic algorithm based on the Iterated Greedy (IG) framework hybridized with a new local search strategy to tackle the 2DBMP. Particularly, we propose different designs for the main IG procedures (i.e., construction, destruction, and reconstruction) based on the trade-off between intensification and diversification. Addi-tionally, the improvement method incorporates three advanced strategies: an efficient way to evaluate the objective function of neighbor solutions, a tiebreak criterion to deal with flat landscapes, and a neigh-borhood reduction technique. Extensive experimentation was carried out to assess the IG performance over state-of-the-art methods, emerging our approach as the most competitive algorithm. Specifically, IG finds the best solutions for all instances considered in considerably less execution time. Statistical tests corroborate the merit of our proposal.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )
Keyword:
Heuristics
Graph layout problem
Iterated greedy
Combinatorial optimization
Bandwidth
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
Reduced white matter microstructural integrity correlates with cognitive deficits in minimal hepatic encephalopathy轻度肝性脑病中白质微结构完整性降低与认知缺陷相关.png)
Gut
GutIF0
PREAI
分享收藏An Iterated Three-Phase Search Approach for Solving the Cyclic Bandwidth ProblemIEEE ACCESSOAAI
IEEE ACCESSIF3.6
OAAI分享收藏分享收藏An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
PREAI
分享收藏Concurrent Signals and Behavioral Plasticity in Blue Crab (Callinectes sapidus Rathbun) CourtshipOAAI
OAAI分享收藏Insulin Pump Therapy in Adolescents With Very Poor Glycemic Control During a 12-Month Cohort TrialOAAI
OAAI分享收藏
查看更多内容