@article{ART002109882},
author={Sang-Un, Lee},
title={Linear Time Algorithm for Network Reliability Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2016},
volume={21},
number={5},
pages={73-77}
TY - JOUR
AU - Sang-Un, Lee
TI - Linear Time Algorithm for Network Reliability Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2016
VL - 21
IS - 5
PB - The Korean Society Of Computer And Information
SP - 73
EP - 77
SN - 1598-849X
AB - This paper deals with the network reliability problem that decides the communication line between main two districts while the districts were destroyed in military communication network that the communication lines are connected in districts. For this problem, there is only in used the mathematical approach as linear programming (LP) software package and has been unknown the polynomial time algorithm. In this paper we suggest the heuristic algorithm with linear time complexity to solve the optimal solution for this problem. This paper suggests the flow path algorithm (FPA) and level path algorithm (LPA). The FPA is to search the maximum number of distinct paths between two districts. The LPA is to construct the levels and delete the unnecessary nodes and edges. The proposed algorithm can be get the same optimal solution as LP for experimental data.
KW - Network reliability;Distinct path;Set cover;Flow path;Level path
DO -
UR -
ER -
Sang-Un, Lee. (2016). Linear Time Algorithm for Network Reliability Problem. Journal of The Korea Society of Computer and Information, 21(5), 73-77.
Sang-Un, Lee. 2016, "Linear Time Algorithm for Network Reliability Problem", Journal of The Korea Society of Computer and Information, vol.21, no.5 pp.73-77.
Sang-Un, Lee "Linear Time Algorithm for Network Reliability Problem" Journal of The Korea Society of Computer and Information 21.5 pp.73-77 (2016) : 73.
Sang-Un, Lee. Linear Time Algorithm for Network Reliability Problem. 2016; 21(5), 73-77.
Sang-Un, Lee. "Linear Time Algorithm for Network Reliability Problem" Journal of The Korea Society of Computer and Information 21, no.5 (2016) : 73-77.
Sang-Un, Lee. Linear Time Algorithm for Network Reliability Problem. Journal of The Korea Society of Computer and Information, 21(5), 73-77.
Sang-Un, Lee. Linear Time Algorithm for Network Reliability Problem. Journal of The Korea Society of Computer and Information. 2016; 21(5) 73-77.
Sang-Un, Lee. Linear Time Algorithm for Network Reliability Problem. 2016; 21(5), 73-77.
Sang-Un, Lee. "Linear Time Algorithm for Network Reliability Problem" Journal of The Korea Society of Computer and Information 21, no.5 (2016) : 73-77.
