Breakout local search for the cyclic cutwidth minimization problem

Mu He (), Qinghua Wu () and Yongliang Lu ()
Additional contact information
Mu He: Huazhong University of Science and Technology
Qinghua Wu: Huazhong University of Science and Technology
Yongliang Lu: Fuzhou University

Journal of Heuristics, 2022, vol. 28, issue 5, No 1, 583-618

Abstract: Abstract The cyclic cutwidth minimization problem (CCMP) is a graph layout problem that involves embedding a graph onto a circle to minimize the maximum cutwidth of the graph. In this paper, we present breakout local search (BLS) for solving CCMP, which combines a dedicated local search procedure to discover high-quality local optimal solutions and an adaptive diversification strategy to escape from local optima. Extensive computational results on a wide set of 179 publicly available benchmark instances show that the proposed BLS algorithm has excellent performance with respect to the best-performing state-of-the-art approaches in terms of solution quality and computational time. In particular, it reports improved best-known solutions for 31 instances, while finding matching best-known results on 139 instances.

Keywords: Heuristics; Cyclic cutwidth; Graph layout problem; Adaptive diversification (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09504-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:5:d:10.1007_s10732-022-09504-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09504-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().