Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 15 / Issue 14

available in:   PDF (392 kB) PS (489 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-015-14-2747


Optimal Serverless Networks Attacks, Complexity and some Approximate Algorithms

Carlos Aguirre (Universidad Autónoma de Madrid, Spain)

Ramon Huerta (University of California, USA)

Lev Tsimring (University of California, USA)

Abstract: A network attack is a set of network elements that are disabled by an adversary. The goal for the attack is to produce the most possible damage to the network in terms of network connectivity by disabling the least possible number of network elements. We show that the problem of finding the optimal attack in a serverless network is NP-Complete even when only edges or nodes are considered for disabling. We study a node attack policy with polynomial complexity based on shorter paths and show that this attack policy outperforms in most cases classical attacks policies such as random attack or maximum degree attack. We also study the behavior of different network topologies under these attack policies.

Keywords: NP-complete attack strategies, network connectivity, optimal attack problem

Categories: C.2.1, F.2.2, G.2.2