Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem

DOI10.1016/j.ejor.2019.07.013zbMath1487.90627OpenAlexW2958858865MaRDI QIDQ2029285

Vinícius Gandra Martins Santos, Marco Antonio M. Carvalho

Publication date: 3 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2019.07.013

zbMATH Keywords

heuristicscombinatorial optimizationcutwidthadaptive large neighborhood searchgraph layout

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A survey of adaptive large neighborhood search algorithms and applications, Strong SDP based bounds on the cutwidth of a graph

Uses Software

• MatrixMarket
• irace
• CPU Benchmarks

Cites Work

• Unnamed Item
• Unnamed Item
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• A hybrid method for the probabilistic maximal covering location-allocation problem
• Branch and bound for the cutwidth minimization problem
• Variable neighborhood search for the vertex separation problem
• On minimizing width in linear layouts
• Antibandwidth and cyclic antibandwidth of meshes and hypercubes
• GRASP and path relinking for the max-min diversity problem
• Min Cut is NP-complete for edge weighted trees
• Narrowness, pathwidth, and their application in natural language processing
• Some simplified NP-complete graph problems
• GRASP and path relinking for the matrix bandwidth minimization.
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Cutwidth: obstructions and algorithmic aspects
• Scatter search for the cutwidth minimization problem
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• A branch and bound algorithm for the matrix bandwidth minimization
• Approximating Layout Problems on Random Geometric Graphs
• One-dimensional logic gate assignment and interval graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Topological Bandwidth
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• A polynomial algorithm for the min-cut linear arrangement of trees
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Complexity Results for Bandwidth Minimization
• Cutwidth of the de Bruijn graph
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• An analysis of variance test for normality (complete samples)
• Parallel variable neighbourhood search strategies for the cutwidth minimization problem