Geodesic
Variable Neighborhood Search for Minimum Linear Arrangement Problem
Yugoslav journal of operations research, Tome 26 (2016) no. 1, p. 3 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

The minimum linear arrangement problem is widely used and studied in many practical and theoretical applications. It consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. This problem is one among the classical NP-hard optimization problems and therefore, there has been extensive research on exact and approximative algorithms. In this paper we present an implementation of a variable neighbor- hood search (VNS) for solving minimum linear arrangement problem. We use Skewed general VNS scheme witch appeared to be successful in solving some recent optimization problems on graphs. Based on computational experiments, we argue that our approach is comparable with the state-of-the-art heuristic.
Classification : 90B06, 90C05, 90C08
Keywords: Graphs, Optimization, Minimum linear arrangement problem, Variable neighborhood search. 
@article{YJOR_2016_26_1_a0,
     author = {Nenad Mladenovi\'c and Dragan Uro\v{s}evi\'c and Dionisio P\'erez-Brit},
     title = {Variable {Neighborhood} {Search} for {Minimum} {Linear} {Arrangement} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {3 },
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a0/}
}
TY  - JOUR
AU  - Nenad Mladenović
AU  - Dragan Urošević
AU  - Dionisio Pérez-Brit
TI  - Variable Neighborhood Search for Minimum Linear Arrangement Problem
JO  - Yugoslav journal of operations research
PY  - 2016
SP  - 3 
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a0/
LA  - en
ID  - YJOR_2016_26_1_a0
ER  - 
%0 Journal Article
%A Nenad Mladenović
%A Dragan Urošević
%A Dionisio Pérez-Brit
%T Variable Neighborhood Search for Minimum Linear Arrangement Problem
%J Yugoslav journal of operations research
%D 2016
%P 3 
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a0/
%G en
%F YJOR_2016_26_1_a0
Nenad Mladenović; Dragan Urošević; Dionisio Pérez-Brit. Variable Neighborhood Search for Minimum Linear Arrangement Problem. Yugoslav journal of operations research, Tome 26 (2016) no. 1, p. 3 . http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a0/