본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

링 네트워크에서의 서버 단절문제에 대한 해법
The Server Disconnection Problem on a Ring Network

명영수    (단국대학교 천안캠퍼스 경영학부  );
  • 초록

    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.


  • 주제어

    k-Server Disconnection Problem .   Combinatorial Optimization.  

  • 참고문헌 (10)

    1. Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., Yannakakis, M. (1994), The complexity of multi-terminal cuts, SIAM J. Computing, 23, 864-894 
    2. Myung, Y. -S. (2007), Algorithms for maximum integer multiflow and multicut in a ring network, Journal of Korean OR and MS society, 32, 89-97 
    3. Myung, Y. -S. (2008), A survey on network survivability models, Journal of the Korean Institute of Industrial Engineers, 34, 181-189     
    4. Vazirani, V. V. (2001) Approximation Algorithms, Springer, Berlin, 2001 
    5. Garg, N., Vazirani, V. V., Yannakakis, M., Primal-dual approximation algorithms for integral flow and milticut in trees (1997), Algorithmica, 18, 3-20 
    6. Costa, M. -C., Letocart, L., Roupin, F. (2003), A greedy algorithm for multicut and integral multiflow in rooted trees, Operations Research Letters, 31, 21-27 
    7. Suzuki, H., Ishiguro, A., and Nishizeki, T. (1992), Variable-priority queue and doghnut routing, Journal of Algorithms, 13, 606-635 
    8. Wu, T. (1992), Fiber network survivability, Artech House, Inc. 
    9. Cosares, S., Deutch, N. D., Saniee, I., and Wasem, O. J. (1995), SONET toolkit : A decision support system for designing robust and cost-effective fiber-optic networks, Interfaces, 25, 20-40 
    10. Hong, S. -P. and Choi, B. -C. (2007), Approximability of the k-server disconnection problem, Networks, 50, 273-282 

 저자의 다른 논문

  • 명영수 (21)

    1. 1984 "경영의사결정을 위한 계량적 모델수립" 經營 科學의 應用 1 (1): 5~9    
    2. 1986 "설비용량에 제한이 있는 입지선정 문제에 대한 기존해법간의 비교분석" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 11 (2): 1~6    
    3. 1993 "노드채색문제에 대한 기존 해법의 분석 및 분류" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 18 (3): 35~49    
    4. 1996 "장애극복형 네트워크 설계에 관한 연구" 산업공학 = IE Interfaces 9 (3): 72~80    
    5. 1998 "정수단위로만 루팅이 허용되는 SONET 링의 용량결정문제" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 23 (3): 49~62    
    6. 2001 "SDP의 개관: 쌍대성, 계산복잡성 및 응용" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 26 (2): 13~46    
    7. 2001 "흐름량을 고려한 네트워크 생존도 계산방법에 관한 연구" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 26 (3): 65~77    
    8. 2001 "Projections of Extended Formulations with precedence Variables for the Asymmetric Traveling Salesman Problem" International journal of management science 7 (2): 1~11    
    9. 2001 "분할이 허용된 SONET 링의 루팅 해법들에 대한 비교 분석" 經營 科學 = Korean management science review 18 (2): 107~116    
    10. 2001 "분할 루팅이 허용되는 링의 용량결정문제에 대한 개선된 해법" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 26 (4): 99~108    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기