Forêts déductibles maximales

Miklos Molnar 1 Raymond Marie 1
1 ARMOR - Architectures and network models
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes, Ecole Nationale Supérieure des Télécommunications de Bretagne
Résumé : Certaines heuristiques de construction d'arbres couvrants partiels de poids minimal d'un ensemble de n\oeuds soulèvent la question suivante : quelle partie de l'arbre d'origine faut-il supprimer lors de l'amélioration d'un arbre couvrant partiel existant par ajout d'un sous-arbre couvrant partiel plus avantageux ? Pour les algorithmes travaillant sur un graphe complet, une réponse (facilement calculable) a été formulée. Dans notre travail, nous généralisons le problème. Dans le cas général, la structure qui peut être supprimée d'un arbre après l'ajout d'un autre arbre (pour retrouver un arbre couvrant un ensemble donné de noeuds) est une forêt. Nous donnons ici une méthode de réduction du problème posé ainsi que la solution algorithmique pour identifier la forêt déductible maximale.
Type de document :
Rapport
[Rapport de recherche] RR-3974, INRIA. 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00072674
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:33:32
Dernière modification le : mercredi 11 avril 2018 - 02:00:41
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:17:51

Fichiers

Identifiants

  • HAL Id : inria-00072674, version 1

Citation

Miklos Molnar, Raymond Marie. Forêts déductibles maximales. [Rapport de recherche] RR-3974, INRIA. 2000. 〈inria-00072674〉

Partager

Métriques

Consultations de la notice

403

Téléchargements de fichiers

115