The complexity of computing the 2-K-reliability in networks

DOI10.1016/J.IPL.2014.03.010MaRDI QIDQ2448852zbMATH OpenOpenAlexFDO

Authors Eduardo A. Canale, Héctor Cancela, Pablo Sartor, Franco Robledo

Publication date 5 May 2014

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

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

zbMATH Keywords

combinatorial problemscomputational complexitydiameter constraintsfault tolerancenetwork reliabilitysurvivability

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18) Reliability, availability, maintenance, inspection in operations research (90B25)

Recommendations

• On computing the 2-diameter-constrained \(K\)-reliability of networks
• Full complexity analysis of the diameter-constrained reliability
• Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior
• Reliability of communication networks with delay constraints: computational complexity and complete topologies
• Diameter constrained reliability of ladders and Spanish fans

Cites work

• scientific article; zbMATH DE number 1735793 (Why is no real title available?)
• New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks
• Reliability of communication networks with delay constraints: computational complexity and complete topologies

Cited in

(5)

• Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems.
• Full complexity analysis of the diameter-constrained reliability
• Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior
• On computing the 2-diameter-constrained \(K\)-reliability of networks
• An O(n*log(n)) algorithm to compute the all-terminal reliability of (K/sub 5/, K/sub 2.2.2/) free networks

This page was built for publication: The complexity of computing the 2-K-reliability in networks

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