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

graph problemsmetaheuristicsvariable neighborhood searchvertex bisection

Mathematics Subject Classification ID

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

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

(13)

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

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)