Etude des problèmes de γ-Clustering.
Antoine Castillon  1@  , Julien Baste, Clarisse Dhaenens, Mohammed Haddad, Hamida Seba@
1 : Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Ecole Centrale de Lille : UMR9189, Université de Lille : UMR9189, Centre National de la Recherche Scientifique : UMR9189

Nous avons introduit les problèmes de γ-Clustering, des variantes du problème Cluster Editing qui permettent de se concentrer sur la détection des sous-graphes denses dans un graphe donné. Formellement on recherche un nombre minimal de modifications à faire sur les arêtes d'un graphe afin d'obtenir une union disjointe de quasi-cliques. Notre étude s'est portée sur la compléxité classique, paramétrée et l'approximabilité de ces problèmes. Nous avons obtenu la classification exhaustive de la compléxité classique de ces problèmes, plusieurs algorithmes FPT paramétrés par la taille de la solution, un algorithme XP paramétré par la tree-width et un résultat de non approximabilité.


Personnes connectées : 2 Vie privée
Chargement...