.png){kind=icon}
.png){kind=icon}
Return
A fast path relinking algorithm for the min-max edge crossing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2024.106603.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The min-max edge crossing problem (MMECP) is a challenging and important problem arising in integratedcircuit design, information visualization, and software engineering. Drawing edges as straight lines in accordance with the hierarchical graph drawing standard, the goal is to reduce the maximum number of edge crossings in graphs. In this study, we propose a fast path relinking (FPR) method based on dynamicprogramming local search to tackle the MMECP, where an efficient neighborhood reduction mechanism is employed to evaluate only the so-called critical vertices instead of all the vertices. Moreover, the proposed FPR can simultaneously manage a number of neighborhood moves at each search iteration, which is significantly different from all the previous approaches based on one neighborhood in the literature. Extensive computational experiments on MMECP instances show that our proposed FPR approach is relatively competitive compared to the best-performing heuristics and the optimization Gurobi solver. In particular, our algorithm improved the best-known solutions for 104 of the 301 publicly available benchmark instances. Additional experiments were conducted to elucidate the key elements and search parameters of the proposed FPR. Furthermore, we made the source code of the algorithm publicly available to facilitate its use in real applications and future research.
Keywords:
Metaheuristics
Min-max edge crossing
Graph drawing
Dynamic programming
Path relinking
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W