2011 · 23 citations · 12 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsFault Tolerance DesignNetwork ConnectivityNetwork Fault ToleranceNetwork OptimizationNetwork ReliabilityReliable System DesignComputational Complexity Of DecompositionConnected Component AnalysisFault Tolerance MetricsFault-tolerant NetworksNetwork DecompositionNetwork Design ProblemsOptimal DesignSize
Connectivity k(G) of a network G is traditionally considered to be the primary metric for evaluation of its fault tolerance capability. However, connectivity as a metric has several limitations - e.g., it has no mechanism to distinguish between localized and random faults. Also it does not provide any information about the network state, if number of failures exceed k(G). The network state information that might be of interest in such a scenario is the size of the largest connected component. In this paper, we address both these limitations and introduce a new metric called region-based largest component size (RBLCS), that provides the largest size of the component in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBLCS for a given network. In addition, we study the problem of least cost design of a network with a target value of RBLCS. We prove that the optimal design problem is NP-complete and present a heuristic to solve the problem. We evaluate our heuristic by comparing its solutions with the optimal solutions. Experimental results demonstrate that our heuristic produces near optimal solution in a fraction of time needed to find the optimal.
12
How to draw a planar graph on a grid
Hubert de Fraysseix, János Pach, Richard Pollack · COMBINATORICA · 1990 · 644 citations
Kapali P. Eswaran, Robert E. Tarjan · SIAM Journal on Computing · 1976 · 310 citations