On the Minimum Average Distance Spanning Tree of the Hypercube

Abstract : 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.
Type de document :
Article dans une revue
Acta Applicandae Mathematicae, Springer Verlag, 2008, 102 (2-3), pp.219-236. 〈10.1007/s10440-008-9215-5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00953604
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 28 février 2014 - 14:10:50
Dernière modification le : jeudi 11 octobre 2018 - 08:48:02

Identifiants

Collections

Citation

Maurice Tchuenté, Paulin Metalia Yonta, Jean-Michel Nlong Ii, Yves Denneulin. On the Minimum Average Distance Spanning Tree of the Hypercube. Acta Applicandae Mathematicae, Springer Verlag, 2008, 102 (2-3), pp.219-236. 〈10.1007/s10440-008-9215-5〉. 〈hal-00953604〉

Partager

Métriques

Consultations de la notice

233