La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A k-Best Paths Algorithm for Highly Reliable Communication Networks A k-Algorithme des meilleurs chemins pour des réseaux de communication hautement fiables

Shi-Wei LEE, Cheng-Shong WU

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans la conception de réseaux de communication hautement fiables, des chemins disjoints entre des paires de nœuds sont souvent nécessaires lors de la phase de conception. Le problème de trouver k des chemins aussi divers que possible et ayant le coût total le plus bas est appelé un k-problème des meilleurs chemins. Nous proposons un algorithme pour trouver le k-meilleurs chemins reliant une paire de nœuds dans un graphique G. L'extension graphique est utilisée pour transférer le k-problème des meilleurs chemins à un problème qui déploie des algorithmes bien connus de flux maximum (MaxFlow) et de flux réseau à coût minimum (MCNF). Nous prouvons le k-la solution des meilleurs chemins de notre algorithme doit être optimale et la complexité temporelle est la même que celle de l'algorithme MCNF. Nos expériences informatiques montrent que l'algorithme proposé peut résoudre k-problème des meilleurs chemins pour un grand réseau dans un temps de calcul raisonnable.

Publication
IEICE TRANSACTIONS on Communications Vol.E82-B No.4 pp.586-590
Date de publication
1999/04/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Réseaux et services de communication

Auteurs

Mots-clés

Table des matières