Description
Date depot: 1 janvier 1900
Titre: Généralisation du Node Cover et Applications
Directeur de thèse:
Walid BENAMEUR (SAMOVAR)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Localiser des fonctions particulières dans un réseau, organiser des communications, étudier la robustesse d'un réseau et sa capacité d'auto-organisation, affecter des ressources, détecter des communautés dans un réseau social ou expliquer certaines de ses propriétés ne sont que quelques exemples de problèmes pratiques qui se ramènent à des problèmes de graphes.
L'objectif de la thèse est d'étudier un nouveau problème de graphes ayant des applications directs dans les réseaux. Plus précisément, nous voulons construire des algorithmes pour déterminer le nombre minimum de nœuds qu'il faut enlever à un graphe (ou réseau) pour que toutes les composantes connexes restantes contiennent chacune au plus k-sommets. Ce problème nouveau (à notre connaissance) est une généralisation du problème de node cover qui correspond au cas k=1 (nombre minimum de sommets intersectant toutes les arêtes du graphe).
Les applications de ce problème sont immédiates. Par exemple, si on installe des anti-virus au niveau des nœuds trouvés, un virus ne pourra pas toucher plus de k nœuds. On peut également voir ce nombre comme une mesure de la robustesse du réseau. Dans un contexte de réseaux sociaux, calculer ce nombre représente une autre alternative pour définir et détecter des communautés sans se baser sur la densité à l’intérieure des communautés. Enfin, on peut également organiser les communications dans un réseau en passant par ce nombre minimal de nœuds en les utilisant comme passerelles entre les composantes connexes.
Sur le plan algorithmique, nous étudierons les méthodes exactes basées sur les approches polyédrales. Nous étudierons également les algorithmes d’approximation avec garantie de performance. Nous n’hésiterons pas à développer des heuristiques pour traiter les problèmes de grandes dimensions. Enfin, nous espérons pouvoir implémenter des approches distribuées qui s’adaptent dynamiquement à l’état du réseau.
Doctorant.e: Mohamed Sidi Mohamed Ahmed