  In this paper, we present algorithms for designing networks that are robust
to node failures with minimal or limited number of links. We present algorithms
for both the static network setting and the dynamic network setting; setting
where new nodes can arrive in the future. For the static setting, we present
algorithms for constructing the optimal network in terms of the number of links
used for a given node size and the number of nodes that can fail. We then
consider the dynamic setting where it is disruptive to remove any of the older
links. For this setting, we present online algorithms for two cases: (i) when
the number of nodes that can fail remains constant and (ii) when only the
proportion of the nodes that can fail remains constant. We show that the
proposed algorithm for the first case saves nearly $3/4$th of the total
possible links at any point of time. We then present algorithms for various
levels of the fraction of the nodes that can fail and characterize their link
usage. We show that when $1/2$ the number of nodes can fail at any point of
time, the proposed algorithm saves nearly $1/2$ of the total possible links at
any point of time. We show that when the number of nodes that can fail is
limited to the fraction $1/(2m)$ ($m \in \mathbb{N}$), the proposed algorithm
saves nearly as much as $(1-1/2m)$ of the total possible links at any point of
time. We also show that when the number of nodes that can fail at any point of
time is $1/2$ of the number of nodes plus $n$, $n \in \mathbb{N}$, the number
of links saved by the proposed algorithm reduces only linearly in $n$. We
conjecture that the saving ratio achieved by the algorithms we present is
optimal for the dynamic setting.

Data Structures and Algorithms;Systems and Control;Systems and Control