Experimental Runtime Results on the Minimum Spanning Tree

F. PEtrot

IBP-Masi 1994/36: Rapport de Recherche Masi / Masi research reports
13 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: Experimental Runtime Results on the Minimum Spanning Tree

Résumé : Ce rapport présente un ensemble d'expérimentations visant à déterminer, parmi les algorithmes connus, la méthode la plus efficace pour le calcul de l'arbre de poids minimal reliant un ensemble de points. Notre intérêt étant dans le calcul de ces arbres 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 caracté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 comporte relativement peu de noeuds, l'algorithme de Prim sur un graphe complet est le plus rapide.

Abstract : 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.

Publications internes Masi 1994 / Masi research reports 1994