Galaxy cutsets in graphs (Q975761)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Galaxy cutsets in graphs |
scientific article |
Statements
Galaxy cutsets in graphs (English)
0 references
11 June 2010
0 references
Given a network \(G=(V(G),E(G))\), a subset of vertices \(S\) of \(V(G)\) that is spanned by a tree of depth at most\( \)r is called to have radius \(r\). The authors discus graphs \(G\) where \(G\) has a cutset that can be written as the union of \(k\) sets of radius \(r\). A cutset which is the union of \(k\) stars is called a galaxy The main result of this paper is the following: It is NP-hard to determine whether a given network contains a galaxy cutset of order \(k\), if k is part of the input.
0 references
network connectivity
0 references
galaxy cutsets
0 references
denial of service attacks
0 references