Neighborhood search based heuristic for the k clustering minimum biclique completion problem
In this paper, we propose the neighborhood search based heuristic to solve the k clustering minimum biclique completion problem. The KCmBCP consists in partitioning a bipartite undirected graph into k clusters such that the total number of edges that added for complete each cluster into a biclique is minimum. Given a bipartite graph G (S, T, E) we consider the problem of finding k bipartite sub graphs, called clusters, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to make each cluster complete is minimized. This problem is known as k clustering minimum biclique completion problem (noted KCmBCP) and has been shown strongly NP hard. The proposed approach begins by construction of an initial solution. After, the proposed approach enters on iterative phase, which destroys part of the initial solution and build of a feasible solution by exploring the neighborhood of the current solution. The experimental results show the effectiveness of the proposed approach.
2016 International Conference on Control, Decision and Information Technologies (CoDIT)