The Complexity of the Residual Node Connectedness Reliability Problem

DOI10.1137/0220009MaRDI QIDQ3204046zbMATH OpenOpenAlexFDO

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

{\#}P-completenessbipartite graphsnetwork reliabilityplanar graphs

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

(20)

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

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)