Resumen de On the Minimum Average Distance Spanning Tree of the Hypercube

Maurice Tchuente, Paulin Melatagia Yonta, Jean-Michel Nlong, Yves Denneulin

• Given an undirected and connected graph G, with a non-negative weight on each edge, the Minimum Average Distance (MAD) spanning tree problem is to find a spanning tree of G which minimizes the average distance between pairs of vertices. This network design problem is known to be NP-hard even when the edge-weights are equal. In this paper we make a step towards the proof of a conjecture stated by A.A. Dobrynin, R. Entringer and I. Gutman in 2001, and which says that the binomial tree B n is a MAD spanning tree of the hypercube H n . More precisely, we show that the binomial tree B n is a local optimum with respect to the 1-move heuristic which, starting from a spanning tree T of the hypercube H n , attempts to improve the average distance between pairs of vertices, by adding an edge e of H n -T and removing an edge e? from the unique cycle created by e. We also present a greedy algorithm which produces good solutions for the MAD spanning tree problem on regular graphs such as the hypercube and the torus.