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

DOI10.1016/j.ipl.2014.10.013zbMath1302.05193OpenAlexW2007703702MaRDI QIDQ477692

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

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

Related Items (1)

Efficient maximum matching algorithms for trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Computing residual connectedness reliability for restricted networks
• On powers of \(m\)-trapezoid graphs
• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• The Complexity of the Residual Node Connectedness Reliability Problem
• Efficient algorithms for computing the reliability of permutation and interval graphs
• The Complexity of Enumeration and Reliability Problems
• Algorithms for K-terminal reliability problems with node failures
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and Pathwidth of Permutation Graphs
• Residual reliability of P-threshold graphs

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