Computational analysis demonstrates polynomial-time resilience calculation in series-parallel networks but intractability in planar networks, highlighting structural limits of network reliability.
The resilience of a network is a measure of its reliability; it is the expected number of node pairs which can communicate. The resilience of an n-vertex series-parallel network can be computed in O(n² ) time. The algorithm employs the recursive structure of maximal series-parallel networks. In contrast to this, computing the resilience of a planar network is shown to be #P-complete.
No takes yet. Share an insight, caveat, or question.
Charles J. Colbourn (1987) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: