Abstract FR:

Nous présentons ici un travail sur le k-partitionnement. Ce domaine a été largement étudié depuis le premier article de Kernighan et Lin [KL70] en 1970. Le problème du k-partitionnement est un problème classique de la théorie des graphes, dont les applications pratiques sont multiples, avec par exemple, la décomposition en domaines des réseaux de communications, pour la conception des circuits VLSI, pour l'exploitation de données. La difficulté de résolution du problème de k-partitionnement vient pour l'essentiel du fait que l'espace des solutions n'est pas convexe et présente par conséquent des optima locaux. Nos solutions à ce problème se basent sur la construction d'arbres couvrants de poids maximum. La procédure ascendante procède par agrégat de fragments. Au départ, chaque noeud forme à lui seul un tel fragment. Par conséquent, la fonction poids d'un fragment étant convexe (c'est une somme d'entiers naturels), on est fondé à optimiser "à la marge". . .