On the Minimum Average Distance Spanning Tree of the Hypercube

• Autores: Maurice Tchuente, Paulin Melatagia Yonta, Jean-Michel Nlong, Yves Denneulin
• Localización: Acta applicandae mathematicae, ISSN 0167-8019, Vol. 102, Nº. 2-3, 2008, págs. 219-236
• Idioma: inglés
• DOI: 10.1007/s10440-008-9215-5
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.