네트워크 단절문제에 대한 상한과 하한을 구하는 해법 = Lower and Upper Bounding Strategies for the Network Disconnection Problem

다국어 초록 (Multilingual Abstract)

The network disconnection problem is to find a set of edges such that the total cost of removing the edges is no more than a given budget and the weight of nodes disconnected from a designated source by removing edges is maximized Martel et al. have shown that the problem with unit capacity and unit demand is NP-hard and Myung and Kim present an integer programming formulation and develop an algorithm that includes a preprocessing procedure and lower and upper bounding strategies In this paper, we present new findings on the properties of the optimal solution and an alternative integer programming formulation, based on which new lower and upper bounding strategies are developed Computational results for evaluating the performance of the proposed algorithm are also presented

참고문헌 (Reference)

1 "Tabu Search-Part II" 2 : 4-32, 1990

2 "Tabu Search-Part I" 1 : 190-206, 1989

3 "SONET toolkit：A decision support system for designing robust and cost-effective fiber-optic networks" 25 : 20-40, 1995

4 "Optimal attack and reinforcement of a network" 32 : 549-561, 1985

5 "Meta Heuristic" Yeongji Moonhwasa 1999.

6 "Mathematical Models and a Heuristic Algorithm for the Graph Disconnection Problem" Korea Advanced Institute of Science and Technology 2003.

7 "Future Paths for Integer Programming and Links to Artificial Intellingence" 5 : 533-540, 1986

8 "Fiber network survivability" Artech House 1992.

9 "Design of survivable networks" North-Holland, 1995.

10 "Design of communication networks with survivability constraints" 45 : 238-252, 1999

11 "Computing the strength of a graph" 20 : 639-654, 1991

12 "Computing the disconnectivity of a graph" UC Davis 2001.

13 "An improved algorithm for the graph disconnection problem" 2003

14 "An algorithm for the graph disconnection problem" Dankook University 2003

15 "A Cutting Plane Algorithm for Computing k-edge Survivability of a Network" 2001.