Linear Time Algorithm for Network Reliability Problem

Sang-Un, Lee

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2016, 21(5), pp.73-77
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹ 강릉원주대학교

ABSTRACT

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.
KEYWORDS

Network reliability , Distinct path , Set cover , Flow path , Level path
REFERENCES (10)

[book] C. Guéret / 2005 / Applications of Optimization with Xpress-MP : 12. 1 Network Reliability / Dash Optimization Ltd : 173~176

[web] M. Edvall / 2009 / Publicity Campaign / Tomlab Optimization Inc / http://tomsym.com/examples/tomsym_networkreliability.html

[report] DTAQ / 2011 / Dictionary of Defense Scientific and Technical Terms / Defense Agency for Technology and Quality

[journal] D. Beasley / 1993 / An Overview of Genetic Algorithms : Part I. Fundamentals / University Computing 15 (2) : 58~69

[journal] C. H. M. Lin / 1983 / An Efficient Algorithm for the Complete Set Partitioning Problem / Discrete Applied Mathematics 6 (2) : 149~156

[report] P. C. Chu / 1996 / A Genetic Algorithm for the Set Partitioning Problem / The Management School; Imperial College : 1~16

[book] M. R. Garey / 1979 / Computers and Intractability: A Guide to the Theory of NP-Completeness / W. H. Freeman & Co.

[book] D. Alevras / 2001 / Universitext / Springer-Verlag

[journal] M. Diaby / 2010 / Linear Programming Formulation of the Set Partitioning Problem / International Journal of Operational Research 8 (4) : 399~427

[journal] B. Lazović / 2012 / An Integer Linear Programming Formulation and Genetic Algorithm for the Maximum Set Splitting Problem / Publications de L’institut Mathenatique 92 (106) : 25~34
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools