Retour aux résultats
Articles (1999), International Transactions in Operational Research, pp. 607-622

Approximating Minimum Spanning Tree of Depth 2

ALFANDARI Laurent , PASCHOS V.

Parmi les problèmes d'optimisation dans des réseaux, le problème de l'arbre recouvrant de coût minimum de profondeur 2 possède de nombreuses applications, parmi lesquelles figure la localisation d'émetteurs d'une entreprise de télécommunications. Nous donnons pour ce problème NP-difficile une heuristique de résolution approchée, dont l'efficacité est validée d'un point de vue à la fois théorique et expérimental. L'algorithme exploite une forme de réduction originale avec le problème classique de Set Covering.

ALFANDARI, L. and PASCHOS, V. (1999). Approximating Minimum Spanning Tree of Depth 2. International Transactions in Operational Research, pp. 607-622.