Counting almost minimum cutsets with reliability applications
From MaRDI portal
Publication:3768663
DOI10.1007/BF02592076zbMath0631.90029MaRDI QIDQ3768663
Charles J. Colbourn, Aparna Ramanathan
Publication date: 1987
Published in: Mathematical Programming (Search for Journal in Brave)
polynomial time algorithmedge-weighted graphnetwork reliabilityinclusion-exclusionprobabilistic graphreliability boundsminimum cardinality network cutsetsnetwork cutsets in a graph
Analysis of algorithms and problem complexity (68Q25) Reliability, availability, maintenance, inspection in operations research (90B25) Applications of graph theory to circuits and networks (94C15)
Related Items
Unnamed Item, Fast sequential importance sampling to estimate the graph reliability polynomial, Practical Minimum Cut Algorithms, Reliable assignments of processors to tasks and factoring on matroids, Optimal cuts in graphs and statistical mechanics, Extracting maximal information about sets of minimum cuts, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on two-terminal network reliability
- The dissection of rectangles into squares
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Calculating bounds on reachability and connectedness in stochastic networks
- The Complexity of Enumeration and Reliability Problems
- Complexity of network reliability computations
- A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
- The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
- Computing the Reliability of Complex Networks
- New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks
- Computing Network Reliability
- Bounds on the Reliability Polynomial for Shellable Independence Systems
- Network reliability analysis: Part I