Computing the K-terminal reliability of directed path graphs

DOI10.1016/J.IPL.2015.05.005MaRDI QIDQ2348708zbMATH OpenOpenAlexFDO

Authors Min-Sheng Lin, Chao-Chun Ting

Publication date 15 June 2015

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

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

zbMATH Keywords

\(K\)-terminal reliabilityalgorithmsdirected path graphsrooted directed path graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Reliability, availability, maintenance, inspection in operations research (90B25)

Recommendations

• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs
• Algorithms for K-terminal reliability problems with node failures
• On reliability of graphs with node failures
• On computing the 2-diameter-constrained \(K\)-reliability of networks

Cites work

• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Efficient algorithms for computing the reliability of permutation and interval graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 815566 (Why is no real title available?)
• Intersection graphs of paths in a tree
• Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems.
• On powers of m-trapezoid graphs
• Reliability covering problems
• The Complexity of Enumeration and Reliability Problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(6)

• A note on bounding \(k\)-terminal reliability
• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Node partition formula for directed graph reliability
• Algorithms for K-terminal reliability problems with node failures
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Finding maximum matchings in RDV graphs efficiently

This page was built for publication: Computing the \(K\)-terminal reliability of directed path graphs

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