A variable neighborhood search approach for the vertex bisection problem

DOI10.1016/J.INS.2018.09.063MaRDI QIDQ2201641zbMATH OpenOpenAlexWikidataFDO

Authors Alberto Herrán, J. Manuel Colmenar, Abraham Duarte

Publication date 29 September 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2018.09.063

zbMATH Keywords

metaheuristicsvariable neighborhood searchgraph problemsvertex bisection

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Two new integer linear programming formulations for the vertex bisection problem
• Variable neighborhood search for the vertex separation problem
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• A modified VNS metaheuristic for max-bisection problems
• An effective multilevel tabu search approach for balanced graph partitioning

Cites work

• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A hybrid heuristic for the \(p\)-median problem
• An efficient memetic algorithm for the graph partitioning problem
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• General variable neighborhood search for computing graph separators
• Greedy randomized adaptive search procedures
• Parallel variable neighbourhood search strategies for the cutwidth minimization problem
• The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width
• Variable neighborhood search for the vertex separation problem
• Variable neighborhood search strategies for the order batching problem
• Variable neighborhood search: Principles and applications
• Variable neighbourhood search: methods and applications
• Vertex Bisection is Hard, too

Cited in

(12)

• Solving the multidimensional maximum bisection problem by a genetic algorithm and variable neighborhood search
• A general variable neighborhood search approach for the minimum load coloring problem
• An efficient variable neighborhood search for the space-free multi-row facility layout problem
• A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
• Variable neighborhood search for edge-ratio network clustering
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Variable neighborhood search for the vertex separation problem
• Variable neighborhood descent applied to multi-way number partitioning problem
• General variable neighborhood search for computing graph separators
• Two new integer linear programming formulations for the vertex bisection problem
• A modified VNS metaheuristic for max-bisection problems
• Polynomial time efficient construction heuristics for vertex separation minimization problem

This page was built for publication: A variable neighborhood search approach for the vertex bisection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201641)