Cellular processing algorithm for the vertex bisection problem: Detailed analysis and new component design

The vertex bisection problem splits a graph G = (V, E) into two sets, L subset of V, vertical bar L vertical bar left perpendicular vertical bar V vertical bar/2 right perpendicular and R = V \ L, such that it minimizes the number of vertices in L connected to R. This problem is a combinatorial NP-hard problem with relevant applications in network communications and, currently, there is only one metaheuristic method that solves it. In this paper, we propose a Cellular Processing Algorithm (CPA) that outperforms the state of the art showing a detailed description of its components and assessing the impact of its main components. Additionally, we include the best-known solutions for the new benchmark of 137 challenging instances. The experimental study, with the new benchmark, shows that the CPA increases the number of best solutions found to 190% and decreases the time to 21% with respect to an efficiency-improved version of the state of the art algorithm. Finally, a non-parametric statistical hypothesis test confirms that the CPA outperforms statistically the efficiency-improved implementation of the state of the art algorithm. (C) 2018 Elsevier Inc. All rights reserved.