Premium
Incorporating dependent node damage in deterministic connectivity analysis and synthesis of networks
Author(s) -
Heffes H.,
Kumar A.
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160106
Subject(s) - survivability , computer science , bounding overwatch , clique , node (physics) , topology (electrical circuits) , graph , theoretical computer science , computer network , mathematics , combinatorics , engineering , structural engineering , artificial intelligence
Abstract Survivability of a node vulnerable network is often assessed in terms of the (node) connectivity of the graph that represents the logical topology of the network. When the damage causing events have widespread impact then, owing to the physical layout of the network facilities, each event can destroy several nodes. As a survivability measure, therefore, we define the generalized connectivity as the minimum number of events (rather than the minimum number of node removals) required to disconnect the network. To model the possible effects of damage causing events, we introduce the notion of a dependence graph on the nodes of the network and a set of admissible cliques in this graph. Nodes that are nonadjacent in the dependence graph are independent, i. e., they cannot be damaged by the same event, and each event destroys an admissible clique of nodes. We present techniques for calculating or bounding the generalized connectivity of given network graphs, and for synthesizing minimum link networks with prescribed generalized connectivity.