Algorithmique des graphes

[haltius]

Bonjour

Je voudrais savoir s'il existe un algorithme permettant de résoudre un problème de bijection de poids maximal dans un graphe bipartie complet, et si oui, pouvez vous me pointer vers la littérature.

J'essaie d'expliquer avec mes mots:

Soit un graphe bipartie G, donc décomposé en 2 sous ensemble de sommets, S1 et S2. J'entends par G "complet" le fait que chaque sommet s de S1 soit relie par une arête a tous les sommets de S2. Bien sur, les sommets de S1 et de S2 ne sont pas reliés entre eux (sinon pas graphe bi partie si je me souviens bien). On affecte donc un poids a chaque arête. Le but est de trouver une bijection (car dans mon cas, S1 et S2 ont le même nombre de sommets mais on pourrait imaginer le cas plus general ou cela n'est pas vrai) de poids maximal, le poids d'une bijection étant la somme des poids de toutes les arêtes de la bijection.

Ya t'il un algo pour resoudre ce probleme? C'est peut etre trivial pour qui s'y connait en graphe :P D'autre part si cet algo existe, est ce qu'il garanti de trouver la solution optimale, ou est ce juste une heuristique d'approximation?


D'avance, merci.

[haltius]

Si ca interesse quelqu'un, apres plus de recherche, j'ai trouvé que ce probleme est connu en anglais sous le nom de "Assignment Problem", et qu'il existe plusieurs algorithmes permettant de le resoudre en temps polynomial.

http://en.wikipedia.org/wiki/Assignment_problem