K-partionnement de graphes du séquentiel au distribué / Lélia Blin ; sous la dir. d'Ivan Lavallée

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 2001

Format : 184 p.

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Graphes, Théorie des

Arbres (théorie des graphes)

Algorithmes

Structures de données (informatique)

Lavallée, Ivan (1946-....) (Directeur de thèse / thesis advisor)

Université de Paris VIII (Organisme de soutenance / degree-grantor)

Résumé / Abstract : 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"...