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
신뢰성이 높은 통신 네트워크 설계에서는 설계 단계에서 노드 쌍 사이의 분리된 경로가 필요한 경우가 많습니다. 찾는 문제 k 최대한 다양하고 총 비용이 가장 낮은 경로를 경로라고 합니다. k-최상의 경로 문제. 우리는 다음을 찾는 알고리즘을 제안합니다. k- 그래프의 노드 쌍을 연결하는 최적의 경로 G. 그래프 확장은 다음을 전송하는 데 사용됩니다. k- 잘 알려진 최대 흐름(MaxFlow) 및 최소 비용 네트워크 흐름(MCNF) 알고리즘을 활용하는 문제에 대한 최선의 경로 문제입니다. 우리는 증명한다 k-우리 알고리즘의 최적 경로 솔루션은 최적이며 시간 복잡도는 MCNF 알고리즘과 동일합니다. 우리의 계산 경험은 제안된 알고리즘이 문제를 해결할 수 있음을 보여줍니다. k- 합리적인 계산 시간 내에 대규모 네트워크에 대한 최상의 경로 문제를 해결합니다.
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.
부
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
부
@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},}
부
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 -