On the Minimum Average Distance Spanning Tree of the Hypercube - Archive ouverte HAL Access content directly
Journal Articles Acta Applicandae Mathematicae Year : 2008

On the Minimum Average Distance Spanning Tree of the Hypercube

(1) , , , (2, 3)
1
2
3

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.
Not file

Dates and versions

hal-00953604 , version 1 (28-02-2014)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More