scientific article; zbMATH DE number 1263176

MaRDI QIDQ4234046zbMATH OpenFDO

Authors David R. Karger

Publication date 29 January 2002

zbMATH Keywords

all-terminal network reliability problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• scientific article; zbMATH DE number 7375995

Cited in

(21)

• A fully polynomial time approximation scheme for minimum cost-reliability ratio problems
• The \(S\)-\textsc{labeling} problem: an algorithmic tour
• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• Integrating and sampling cuts in bounded treewidth graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• The exponential time complexity of computing the probability that a graph is connected
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• scientific article; zbMATH DE number 1490110 (Why is no real title available?)
• Improved bounds and algorithms for graph cuts and network reliability
• Counting and sampling minimum cuts in genus g graphs
• Fast sequential importance sampling to estimate the graph reliability polynomial
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• scientific article; zbMATH DE number 7375995 (Why is no real title available?)
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• An O(n*log(n)) algorithm to compute the all-terminal reliability of (K/sub 5/, K/sub 2.2.2/) free networks
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• D-spectrum and reliability of a binary system with ternary components
• Improved bounds and algorithms for graph cuts and network reliability
• Approximation algorithm for estimating failure probability of multipath transmission
• Computing the Tutte polynomial of a graph of moderate size

This page was built for publication:

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