F. PEtrot Experimental Runtime Results on the Minimum Spanning Tree Ce rapport présente un ensemble d'expérimentations visant à déterminer, parmi les algorithmes connus, la méthode la plus ef­ ficace pour le calcul de l'arbre de poids minimal reliant un en­ semble de points. Notre intérêt étant dans le calcul de ces ar­ bres pour le placement et routage des circuits intégrés VLSI, nous avons limité notre domaine d'investigation aux graphes de moins de 200 noeuds. Les deux types de graphes considérés sont les graphes complets et les graphes issus de la triangulation de Delaunay. Les deux algorithmes expérimentés sont celui de Kruskal et celui de Prim, sur ces deux types de graphes aux car­ actéristiques différentes. Afin d'assurer une certaine généralité à nos conclusions, nous avons fait ces mesures sur quatre architectures matérielles différentes. Le résultat de ces mesures est que, pour la classe de problemes considérée qui com­ porte relativement peu de noeuds, l'algorithme de Prim sur un graphe complet est le plus rapide. The computation of the minimum spanning tree of a set of vertices is extensively used in the layout phase of VLSI circuit design. In that context, it is interesting to indicate clearly the most efficient implementation of the minimum spanning tree on today hardware architecture with today's knowledge. We have done systematic experiments on the two well known Kruskal's and Prim's algorithm, either on complete graphs or on the Delaunay triangulation of random graphs having up to 200 vertices. These experiments have been done on four different computers to ensure reliability. As a result, we show that Prim's algorithm on complete graph is the fastest approach for problems with few vertices like the VLSI ones.