Please use this identifier to cite or link to this item:
Title: The Complexity of the Infinity Replacement Problem in the Cyber Security Model
Authors: Supachai Mukdasanit
Sanpawat Kantabutra
Authors: Supachai Mukdasanit
Sanpawat Kantabutra
Keywords: Computer Science
Issue Date: 21-Aug-2018
Abstract: © 2017 IEEE. In this article we present a new defensive problem on a security system. Let M be a security model (T, C, P), where T = (V, E) is a rooted tree rooted at r, C is a multiset of E(T) costs and P is a multiset of V(T)-1 prizes and let (T, c, p) be a security system, where c and p are bijections c: E(T) C and p: V(T) r P, respectively. Given a budget BZ+, we consider the problem of determining the existence of an edge e E(T), where c(e)=i such that the maximum total of prizes obtained from an optimal attack in the security system (T, c, p) is minimum when i is replaced by ∞. We define the decision and optimization versions of the problem and examine their computational complexities. We prove that the decision problem is NP-hard and provide a pseudopolynomial time algorithm for the optimization version of the problem. Additionally, we show that some restricted instances can be solved in polynomial time. In the end conclusion and an example of the application of the algorithm are given.
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.

Items in CMUIR are protected by copyright, with all rights reserved, unless otherwise indicated.