The Complexity of the Residual Node Connectedness Reliability Problem

DOI10.1137/0220009MaRDI QIDQ3204046zbMATHOpenAlexFDO

Authors K. Sutner, A. Satyanarayana, Charles L. Suffel

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220009

zbMATH Keywords

planar graphsbipartite graphsnetwork reliability{\#}P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Computing residual connectedness reliability for restricted networks
• The complexity of the reliable connectivity problem
• scientific article; zbMATH DE number 176146
• scientific article; zbMATH DE number 139921
• scientific article; zbMATH DE number 176250
• Complexity of Network Reliability and Optimal Resource Placement Problems
• scientific article; zbMATH DE number 6719821
• The connected critical node problem

Cited in

(17)

• On the mean connected induced subgraph order of cographs
• Maximal intervals of decrease and inflection points for node reliability
• Uniformly optimally reliable graphs: A survey
• scientific article; zbMATH DE number 176146 (Why is no real title available?)
• Computing residual connectedness reliability for restricted networks
• The complexity of the reliable connectivity problem
• Residual reliability of P-threshold graphs
• A simple variant of node connectivity is NP-complete
• Computing the number and average size of connected sets in planar 3-trees
• Network Resilience
• The shape of node reliability
• Existence of optimally‐greatest digraphs for strongly connected node reliability
• A survey of some network reliability analysis and synthesis results
• Extremal problems for connected set enumeration
• scientific article; zbMATH DE number 176250 (Why is no real title available?)
• Computing optimal assignments for residual network reliability
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs

This page was built for publication: The Complexity of the Residual Node Connectedness Reliability Problem

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