- HOME
- 홈페이지 이용안내
논문 기본정보
Linear Time Algorithm for Network Reliability Problem
논문 개요
| 기관명 | NDSL |
|---|---|
| 저널명 | 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information |
| ISSN | 1598-849x,2383-9945 |
| ISBN |
논문저자 및 소속기관 정보
| 저자(한글) | |
|---|---|
| 저자(영문) | |
| 소속기관 | |
| 소속기관(영문) | |
| 출판인 | |
| 간행물 번호 | |
| 발행연도 | 2016-01-01 |
| 초록 | This paper deals with the network reliability problem that decides the communication line between main two districts while the k districts were destroyed in military communication network that the n communication lines are connected in m 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 O(n) 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. |
| 원문URL | http://click.ndsl.kr/servlet/OpenAPIDetailView?keyValue=03553784&target=NART&cn=JAKO201617338763049 |
| 첨부파일 |
추가정보
| 과학기술표준분류 | |
|---|---|
| ICT 기술분류 | |
| DDC 분류 | |
| 주제어 (키워드) | Network reliability,Distinct path,Set cover,Flow path,Level path |