링 네트워크에서의 서버 단절문제에 대한 해법

다국어 초록 (Multilingual Abstract)

In the server disconnection problem, a network with m servers and their users is given and an attacker is to destroy a set of edges to maximize his net gain defined as the total disconnected utilities of the users minus the total edge-destruction cost. The problem is known to be NP-hard. In this paper, we study the server disconnection problem restricted to a ring network. We present an efficient combinatorial algorithm that generates an optimal solution in polynomial time.

참고문헌 (Reference)

1 명영수, "링 네트워크에서의 최대 다품종정수흐름문제와 최소 다중절단면문제에 대한 해법" 한국경영과학회 32 (32): 89-97, 2007

2 명영수, "네트워크 생존도 모형 개관" 대한산업공학회 34 (34): 181-189, 2008

3 Suzuki, H., "Variable-priority queue and doghnut routing" 13 : 606-635, 1992

4 Dahlhaus, E., "The complexity of multi-terminal cuts, SIAM J" 23 : 864-894, 1994

5 Cosares, S., "SONET toolkit : A decision support system for designing robust and cost-effective fiber-optic networks" 25 : 20-40, 1995

6 Garg, N., "Primal-dual approximation algorithms for integral flow and milticut in trees" 18 : 3-20, 1997

7 Wu, T., "Fiber network survivability" Artech House 1992

8 Vazirani, V. V., "Approximation Algorithms" Springer 2001

9 Hong, S. -P., "Approximability of the k-server disconnection problem" 50 : 273-282, 2007

10 Costa, M. -C., "A greedy algorithm for multicut and integral multiflow in rooted trees" 31 : 21-27, 2003