A Polynomial-Time Algorithm For The Minimum Diameter Spanning Tree Problem

s. Tricot

IBP-Masi 1994/09: Rapport de Recherche Masi / Masi research reports
13 pages - Mars/March 1994 - Document en anglais.

Titre / Title: A Polynomial-Time Algorithm For The Minimum Diameter Spanning Tree Problem

Résumé : Le diamètre d'un arbre est le plus long chemin élémentaire entre deux points quelconques de l'arbre. Nous présentons ici un algorithme en 0(mn+n2log(n)) pour la recherche d'un arbre de diamètre minimum (MDST) ou d'un arbre de Steiner de diamètre minimum (SMDST) dans un graphe.

Abstract : The diameter of a spanning tree is the longest simple path between any two points of the tree. In this paper, we present a 0(mn+n2log(n))-time algorithm for the Minimum Diameter Spanning Tree (MDST) problem and for the Steiner Minimum Diameter Spanning Tree (SMDST) problem in graphs.

Publications internes Masi 1994 / Masi research reports 1994