Counting almost minimum cutsets with reliability applications

DOI10.1007/BF02592076MaRDI QIDQ3768663zbMATH OpenFDO

Authors Aparna Ramanathan, Charles J. Colbourn

Publication date 1987

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02592076

zbMATH Keywords

edge-weighted graphinclusion-exclusionminimum cardinality network cutsetsnetwork cutsets in a graphnetwork reliabilitypolynomial time algorithmprobabilistic graphreliability bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, availability, maintenance, inspection in operations research (90B25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• scientific article; zbMATH DE number 3900472
• Computing All Small Cuts in an Undirected Network
• Improved bounds and algorithms for graph cuts and network reliability
• Improved bounds and algorithms for graph cuts and network reliability

Cites work

• A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
• Bounds on the Reliability Polynomial for Shellable Independence Systems
• Calculating bounds on reachability and connectedness in stochastic networks
• Complexity of network reliability computations
• Computing Network Reliability
• Computing the Reliability of Complex Networks
• Graph theory with applications
• scientific article; zbMATH DE number 4019092 (Why is no real title available?)
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3947973 (Why is no real title available?)
• scientific article; zbMATH DE number 3523603 (Why is no real title available?)
• Lower bounds on two-terminal network reliability
• Network reliability analysis: Part I
• New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The dissection of rectangles into squares
• The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds

Cited in

(17)

• Extracting maximal information about sets of minimum cuts
• An algorithm for the estimation of minimal cut and path sets from field failure data
• Cut-threshold graphs
• The reliability of systems with stair-type consecutive minimal cuts
• Cut-Set Intersections and Node Partitions
• Reliability of Systems with Consecutive Minimal Cutsets
• scientific article; zbMATH DE number 4068647 (Why is no real title available?)
• Counting Problems Associated With Steiner Trees In Graphs
• Improved bounds and algorithms for graph cuts and network reliability
• Practical minimum cut algorithms
• Fast sequential importance sampling to estimate the graph reliability polynomial
• scientific article; zbMATH DE number 975420 (Why is no real title available?)
• Improved bounds and algorithms for graph cuts and network reliability
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Reliable assignments of processors to tasks and factoring on matroids
• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• Optimal cuts in graphs and statistical mechanics

This page was built for publication: Counting almost minimum cutsets with reliability applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768663)