Publications
Detailed Information
Two-Server Network Disconnection Problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Byung-Cheon | - |
dc.contributor.author | Hong, Sung-Pil | - |
dc.date.accessioned | 2009-07-08T05:37:10Z | - |
dc.date.available | 2009-07-08T05:37:10Z | - |
dc.date.issued | 2006-05 | - |
dc.identifier.citation | Lecture Notes in Computer Science, Vol. 3982/2006 (2006) 785-792 | en |
dc.identifier.isbn | 978-3-540-34075-1 | - |
dc.identifier.issn | 0302-9743 (print) | - |
dc.identifier.issn | 1611-3349 (online) | - |
dc.identifier.uri | https://hdl.handle.net/10371/5330 | - |
dc.description.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. | en |
dc.description.sponsorship | The research was partially supported by KOSEF research fund R01-2005-000-10271-0. | en |
dc.language.iso | en | - |
dc.publisher | Springer Verlag | en |
dc.relation.ispartofseries | Lecture Notes in Computer Science | en |
dc.relation.ispartofseries | Volume 3982/2006 | en |
dc.title | Two-Server Network Disconnection Problem | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 최병천 | - |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.identifier.doi | 10.1007/11751595_83 | - |
dc.identifier.doi | 10.1007/11751595_83 | - |
dc.citation.journaltitle | Lecture Notes in Computer Science = LNCS | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.