| Abstract | Soit G = (V, E, We) un graphe avec des poids sur les arêtes, avec V l'ensemble des sommets, E l'ensemble des arêtes et We une fonc-tion de pondération qui associe à chaque arête e ∈ E un poids posi-tif we ≥ 0. Le problème du sous-graphe de poids maximum des arêtes (MEWS) vise à trouver un sous-graphe H = (S, F) de G tel que la somme des poids des arêtes de F est la plus grande et le nombre des sommets de S égal à k, où k un entier (k ≥ 3), il est prouvé que le MEWS est un problème NP-Complet. Dans ce papier, nous proposons un algorithme recherche tabou multistart pour le MEWS. Nous avons utilisé notre algo-rithme pour résoudre le MEWS dans des réseaux biologiques, qui ont des vrais poids sur les arêtes. Les résultats ont montré que notre algorithme surperforme les autres heuristiques de l'état de l'art. |
|---|
