Résumé de séminaire

Résumé :

Le problème du couplage maximum dans un graphe non-orienté consiste à déterminer un sous-ensemble d'arêtes de cardinalité maximum tel que deux arêtes ne soient pas incidentes au même sommet. Du fait de ces nombreuses applications en optimisation combinatoire et recherche opérationnelle, ce problème a été particulièrement étudié pour les graphes bipartis. Soit G = (S,T,A) un graphe biparti où S = {1,...,n} et T = {1,...,m} forment les deux ensembles de sommets et A est l'ensemble des arêtes. L'algorithme le plus efficace pour trouver un couplage maximum dans un tel graphe biparti est du à Hopcroft et Karp [1] et s'exécute en temps (plus que) quadratique en le nombre de sommets du graphe.

Dans cet exposé, une sous-classe des graphes bipartis, introduite par Glover [2] en 1967, sera considérée: les graphes bipartis convexes. Le graphe biparti G = (S,T,A) est dit T-convexe s'il existe un ordre sur T tel que l'ensemble des sommets de T connectés à un sommet de S apparaissent consécutivement dans cet ordre. Un tel graphe est spécifié en donnant l'ordre < sur T et pour chaque sommet i de S, le plus petit et le plus grand élément de l'intervalle des sommets de T connectés à i. Glover proposa un algorithme glouton pour déterminer un couplage maximum en temps O(|A|) dans ces graphes bipartis convexes. Depuis, plusieurs améliorations ont été proposées permettant d'abaisser la complexité en temps de l'algorithme à O(n A(n) + m) [3] où A(n) est une fonction qui croît très lentement (relative à l'inverse de la fonction d'Ackermann) ou encore O(n log n) [4], et même plus récemment à O(n) [5]. Malheureusement, mis à part l'heuristique originelle de Glover, tous ces algorithmes utilisent des structures de données spéciales (comme les tas par exemple), qui les rendent difficiles à mettre en oeuvre. Après avoir commenté ces améliorations successives, nous proposerons un algorithme très simple à programmer dont le temps d'exécution est dans le pire des cas O(n log n).

Références :

[1] J.E. Hopcroft et R.M. Karp (1973). An n^{5/2} algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2, 225--231.

[2] F. Glover (1967). Maximum matchings in a convex bipartite graph. Naval Research Logistics Quarterly 4(3), 313--316.

[3] W. Lipski et F.P. Preparata (1981). Efficient algorithms for maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15, 329--346.

[4] G. Gallo (1984). An O(n log n) algorithm for the convex bipartite matching problem. Operations Research Letters 3(1), 31--34.

[5] G. Steiner et J.S. Yeomans (1996). A linear time algorithm for maximum matchings in convex, bipartite graphs. Computers and Mathematics with Applications, 31(12), 91--96.