The Complexity of Reliability Computations in Planar and Acyclic Graphs
From MaRDI portal
Publication:3745304
DOI10.1137/0215050zbMath0606.68066OpenAlexW4298367105MaRDI QIDQ3745304
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.17615/b4xs-xn96
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (25)
Sixty years of network reliability ⋮ A graph theoretical approach to the firebreak locating problem ⋮ The computational complexity of the reliability problem on distributed systems ⋮ Network reliability and the probabilistic estimation of damage from fire spread ⋮ Computing optimal assignments for residual network reliability ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks ⋮ The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ Measuring the distance to series-parallelity by path expressions ⋮ Network Resilience ⋮ Combinatorial aspects of network reliability ⋮ Invulnerability of planar two-tree networks ⋮ A factoring approach for the stochastic shortest path problem ⋮ An algorithm to compute the all-terminal reliability measure. ⋮ Computing residual connectedness reliability for restricted networks ⋮ Tutte polynomials computable in polynomial time ⋮ A proof of unimodality on the numbers of connected spanning subgraphs in an \(n\)-vertex graph with at least \(\left\lceil (3-2\sqrt 2) n^2 + n - \frac {7-2\sqrt 2}{2 \sqrt 2}\right\rceil\) edges ⋮ The distributed program reliability analysis on ring-type topologies ⋮ Computational complexity of impact size estimation for spreading processes on networks ⋮ A survey of some network reliability analysis and synthesis results ⋮ On the computational complexity of the Jones and Tutte polynomials ⋮ High-confidence estimation of small s -t reliabilities in directed acyclic networks ⋮ MULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKS ⋮ Renewal Networks: Connectivity and Reachability on a Time Interval ⋮ Network reliability: Numbers or insight? (A discussion paper)
This page was built for publication: The Complexity of Reliability Computations in Planar and Acyclic Graphs
