SHERP

Two-Server Network Disconnection Problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Choi, Byung-Cheon; Hong, Sung-Pil
Issue Date
2006-05
Publisher
Springer Verlag
Citation
Lecture Notes in Computer Science, Vol. 3982/2006 (2006) 785-792
Abstract
Consider a set of users and servers connected by a network. Each server provides a unique service which is of certain benefit to each user. Now comes an attacker, who wishes to destroy a set of edges of the network in the fashion that maximizes his net gain, namely, the total disconnected benefit of users minus the total edge-destruction cost. We first discuss that the problem is polynomially solvable in the single-server case. In the multiple-server case, we will show, the problem is, however, NP-hard. In particular, when there are only two servers, the network disconnection problem becomes intractable. Then a -approximation algorithm is developed for the two-server case.
ISSN
0302-9743 (print)
1611-3349 (online)
Language
English
URI
http://hdl.handle.net/10371/5330
DOI
https://doi.org/10.1007/11751595_83

https://doi.org/10.1007/11751595_83
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse