Please use this identifier to cite or link to this item:
Title: Attack and defense in the layered cyber-security model and their (1 ± ϵ)-approximation schemes
Authors: Supachai Mukdasanit
Sanpawat Kantabutra
Authors: Supachai Mukdasanit
Sanpawat Kantabutra
Keywords: Computer Science;Mathematics
Issue Date: 1-Feb-2021
Abstract: © 2020 Elsevier Inc. Let M=(T,C,P) be a security model, where T is a rooted tree, C is a multiset of costs and P is a multiset of prizes and let (T,c,p) be a security system, where c and p are bijections of costs and prizes. The problems of computing an optimal attack on a security system and of determining an edge e∈E(T) such that the maximum sum of prizes obtained from an optimal attack in (T,c,p) is minimized when c(e)=∞ are considered. An O(G2n)-time algorithm to compute an optimal attack as well as an O(G2n2)-time algorithm to determine such an edge are given, in addition to a (1-ϵ) FPTAS with the time bound [Formula presented] and a (1+ϵ) FPTAS with the time bound [Formula presented] for the first and second problems, respectively.
ISSN: 10902724
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.