Algorithme de k-partitionnement auto-stabilisant et compétitif

International audienceNous proposons un algorithme auto-stabilisant qui calcule un k-partitionnement de taille O(n) dans un réseau quelconque de n processus. Lorsque le réseau est un graphe de disques unitaires, le k-partitionnement calculé est au plus 7,2552 k + O(1) fois plus grand que le minimum possible. Lorsque le réseau est un graphe de disques quasi-unitaires de paramètre λ, le k-partitionnement calculé est au plus 7,2552 k λ² + O(λ) fois plus grand que le minimum possible