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

DOI10.1016/J.IPL.2014.10.013zbMATH Open1302.05193OpenAlexW2007703702MaRDI QIDQ477692FDOQ477692

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

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

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)

Cites Work

• The Complexity of Enumeration and Reliability Problems
• Title not available (Why is that?)
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• 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
• Algorithms for K-terminal reliability problems with node failures
• Title not available (Why is that?)
• Residual reliability of P-threshold graphs
• Computing residual connectedness reliability for restricted networks

Cited In (5)

• 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)