Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula

DOI10.1155/S1024123X98000817MaRDI QIDQ1294685zbMATH OpenOpenAlexFDO

Authors Laura Schoppmann, Thomas J. jun. Marlowe

Publication date 9 August 1999

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/48486

zbMATH Keywords

computational complexitygraphsnetworksreliabilitythreshold graphsefficient recursive algorithmsGilbert's formulapolynomial-time computations

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Reliability, availability, maintenance, inspection in operations research (90B25)

Recommendations

• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• On an Invariant of Graphs and the Reliability Polynomial
• Speeding up computation of the reliability polynomial coefficients for a random graph
• scientific article; zbMATH DE number 2077106
• Reliability polynomials and their asymptotic limits for families of graphs
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• A recurrence formula for unreliability polynomial of graphs
• An upper bound on the independence number of a graph computable in polynomial-time
• Efficient algorithms for computing the reliability of permutation and interval graphs

Cited in

(1)

• Efficient algorithms for computing the reliability of permutation and interval graphs

This page was built for publication: Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula

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