A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

DOI10.1016/J.IPL.2014.10.013MaRDI QIDQ477692zbMATH OpenOpenAlexFDO

Authors Min-Sheng Lin, Chao-Chun Ting

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.10.013

zbMATH Keywords

algorithmscombinatorial problems\(d\)-trapezoid graphs\(K\)-terminal residual reliability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Reliability, availability, maintenance, inspection in operations research (90B25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Computing the \(K\)-terminal reliability of directed path graphs
• Algorithms for K-terminal reliability problems with node failures
• scientific article; zbMATH DE number 1263176
• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks

Cites work

• scientific article; zbMATH DE number 3598539 (Why is no real title available?)
• scientific article; zbMATH DE number 815566 (Why is no real title available?)
• Algorithms for K-terminal reliability problems with node failures
• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Computing residual connectedness reliability for restricted networks
• Efficient algorithms for computing the reliability of permutation and interval graphs
• On powers of m-trapezoid graphs
• Residual reliability of P-threshold graphs
• The Complexity of Enumeration and Reliability Problems
• The Complexity of the Residual Node Connectedness Reliability Problem
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(6)

• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Algorithms for K-terminal reliability problems with node failures
• Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula
• Residual reliability of P-threshold graphs
• Computing the \(K\)-terminal reliability of directed path graphs
• Efficient maximum matching algorithms for trapezoid graphs

This page was built for publication: A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs

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