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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Shi-Wei LEE, Cheng-Shong WU, "A k-Best Paths Algorithm for Highly Reliable Communication Networks" in IEICE TRANSACTIONS on Communications,
vol. E82-B, no. 4, pp. 586-590, April 1999, doi: .
Abstract: In highly reliable communication network design, disjoint paths between pairs of nodes are often needed in the design phase. The problem of finding k paths which are as diverse as possible and have the lowest total cost is called a k-best paths problem. We propose an algorithm for finding the k-best paths connecting a pair of nodes in a graph G. Graph extension is used to transfer the k-best paths problem to a problem which deploits well-known maximum flow (MaxFlow) and minimum cost network flow (MCNF) algorithms. We prove the k-best paths solution of our algorithm to be an optimal one and the time complexity is the same as MCNF algorithm. Our computational experiences show that the proposed algorithm can solve k-best paths problem for a large network within reasonable computation time.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e82-b_4_586/_p
Copier
@ARTICLE{e82-b_4_586,
author={Shi-Wei LEE, Cheng-Shong WU, },
journal={IEICE TRANSACTIONS on Communications},
title={A k-Best Paths Algorithm for Highly Reliable Communication Networks},
year={1999},
volume={E82-B},
number={4},
pages={586-590},
abstract={In highly reliable communication network design, disjoint paths between pairs of nodes are often needed in the design phase. The problem of finding k paths which are as diverse as possible and have the lowest total cost is called a k-best paths problem. We propose an algorithm for finding the k-best paths connecting a pair of nodes in a graph G. Graph extension is used to transfer the k-best paths problem to a problem which deploits well-known maximum flow (MaxFlow) and minimum cost network flow (MCNF) algorithms. We prove the k-best paths solution of our algorithm to be an optimal one and the time complexity is the same as MCNF algorithm. Our computational experiences show that the proposed algorithm can solve k-best paths problem for a large network within reasonable computation time.},
keywords={},
doi={},
ISSN={},
month={April},}
Copier
TY - JOUR
TI - A k-Best Paths Algorithm for Highly Reliable Communication Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 586
EP - 590
AU - Shi-Wei LEE
AU - Cheng-Shong WU
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E82-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 1999
AB - In highly reliable communication network design, disjoint paths between pairs of nodes are often needed in the design phase. The problem of finding k paths which are as diverse as possible and have the lowest total cost is called a k-best paths problem. We propose an algorithm for finding the k-best paths connecting a pair of nodes in a graph G. Graph extension is used to transfer the k-best paths problem to a problem which deploits well-known maximum flow (MaxFlow) and minimum cost network flow (MCNF) algorithms. We prove the k-best paths solution of our algorithm to be an optimal one and the time complexity is the same as MCNF algorithm. Our computational experiences show that the proposed algorithm can solve k-best paths problem for a large network within reasonable computation time.
ER -