Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Neighborhood Search-based Heuristic for the K-Clustering Minimum Biclique Completion Problem

Abstract : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:20
Dernière modification le : jeudi 24 mars 2022 - 03:00:26


  • HAL Id : hal-03617905, version 1



Najat Al-Iedani, Mhand Hifi, Toufik Saadi. Neighborhood Search-based Heuristic for the K-Clustering Minimum Biclique Completion Problem. 2016 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Apr 2016, Saint Pauls Bay, Malta. pp.639-643. ⟨hal-03617905⟩



Consultations de la notice