Variable neighborhood search for the vertex separation problem

DOI10.1016/j.cor.2012.04.017zbMath1349.90809OpenAlexW1967700023WikidataQ57856250 ScholiaQ57856250MaRDI QIDQ339678

Rafael Martí, Jesús Sánchez-Oro, Abraham Duarte, Nenad Mladenović, Juan José Pantrigo, Laureano Fernando Escudero Bueno

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.04.017

zbMATH Keywords

combinatorial optimizationmetaheuristicslayout problemsvariable neigborhood search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Parallel variable neighborhood search for the min–max order batching problem, Solving dynamic memory allocation problems in embedded systems with parallel variable neighborhood search strategies, Two metaheuristic approaches for solving multidimensional two-way number partitioning problem, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, General variable neighborhood search for computing graph separators, Polynomial time efficient construction heuristics for vertex separation minimization problem, Multi-objective variable neighborhood search: an application to combinatorial optimization problems, Approaching the rank aggregation problem by local search-based metaheuristics, Population-based iterated greedy algorithm for the S-labeling problem, On integer linear programs for treewidth based on perfect elimination orderings, A variable neighborhood search approach for the vertex bisection problem, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, An experimental comparison of Variable Neighborhood Search variants for the minimization of the vertex-cut in layout problems, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, A general variable neighborhood search for the cyclic antibandwidth problem

Uses Software

• CPLEX

Cites Work

• Computing the vertex separation of unicyclic graphs
• On the parameterized complexity of layered graph drawing
• Variable neighbourhood search: methods and applications
• Antibandwidth and cyclic antibandwidth of meshes and hypercubes
• GRASP and path relinking for the max-min diversity problem
• Pathwidth of cubic graphs and exact algorithms
• Interval graphs and searching
• Min Cut is NP-complete for edge weighted trees
• Black-white pebbles and graph separation
• Edge-isoperimetric inequalities in the grid
• The vertex separation number of a graph equals its path-width
• On the pathwidth of chordal graphs
• The vertex separation and search number of a graph
• Obstruction set isolation for the gate matrix layout problem
• On search, decision, and the efficiency of polynomial-time algorithms
• Variable neighborhood search
• Scatter search for the cutwidth minimization problem
• Searching and pebbling
• Approximating Layout Problems on Random Geometric Graphs
• GRASP with path relinking heuristics for the antibandwidth problem
• A Separator Theorem for Planar Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Treewidth and Pathwidth of Permutation Graphs
• The pathwidth and treewidth of cographs
• Unnamed Item
• Unnamed Item
• Unnamed Item