A k-Best Paths Algorithm for Highly Reliable Communication Networks
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E82-B No.4 pp.586-590
- Publication Date
- 1999/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Communication Networks and Services
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
