The Complexity of the Residual Node Connectedness Reliability Problem

DOI10.1137/0220009zbMATH Open0716.68049OpenAlexW2093187872MaRDI QIDQ3204046FDOQ3204046

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

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
• The connected critical node problem

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)

Cited In (17)

• On the Mean Connected Induced Subgraph Order of Cographs
• A simple variant of node connectivity is NP-complete
• Existence of optimally‐greatest digraphs for strongly connected node reliability
• Maximal intervals of decrease and inflection points for node reliability
• Extremal problems for connected set enumeration
• Title not available (Why is that?)
• The shape of node reliability
• A survey of some network reliability analysis and synthesis results
• Residual reliability of P-threshold graphs
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Title not available (Why is that?)
• Computing residual connectedness reliability for restricted networks
• Uniformly optimally reliable graphs: A survey
• The complexity of the reliable connectivity problem
• Computing the number and average size of connected sets in planar 3-trees
• Computing optimal assignments for residual network reliability
• Network Resilience

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)