Neighborhood Search-based Heuristic for the K-Clustering Minimum Biclique Completion Problem - Université de Picardie Jules Verne Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

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

Najat Al-Iedani
  • Fonction : Auteur
  • PersonId : 1231166
  • IdRef : 23638418X

Résumé

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.
Fichier non déposé

Dates et versions

hal-03617905 , version 1 (23-03-2022)

Identifiants

  • HAL Id : hal-03617905 , version 1

Citer

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⟩

Collections

U-PICARDIE EPROAD
9 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More