scientific article; zbMATH DE number 3884207
Consider finite simple undirected graphs with N vertices and connectivity m in which each vertex has a probability p of failure (removal with its incident edges). Assume that failures of vertices are independent. \textit{H. Frank} [Proc. 3rd Annual Princeton Conf. Inform. Sci. Syst., 1-6 (1969; Zbl 0293.05143)] has described the problem of finding, if p is sufficiently small, graphs with the minimum probability of disconnection among all graphs with mN/2 edges. The author has previously shown that in many cases it is possible to answer Frank's question by constructing a graph with the minimum number of vertex cut sets. He now considers the problem of minimising the expected number E of vertices disconnected from the largest remaining component of the graph (or isolated if all components are isolated vertices). Some graphs constructed by \textit{S. l. Hakimi} and \textit{A. T. Amin} [Networks 3, 241- 260 (1973; Zbl 0272.05124)] have the smallest value of E for some sufficiently small p. However, their result does not indicate how small p must be. The author gives what may be a more practical solution to the problem of minimising E.
- Extensions de réseaux de connexité donnée. (Extensions of graphs of given connectivity)
- Optimally reliable networks
- A note on the bounded fragmentation property and its applications in network reliability
- Lower bound on the reliability of a network with a 2-connected structure
- On the robustness of interconnections in random graphs: a symbolic approach.
- Reliabilities for two kinds of graphs with smaller diameters
- On the construction of optimally reliable graphs
- scientific article; zbMATH DE number 3871399 (Why is no real title available?)
- scientific article; zbMATH DE number 4213723 (Why is no real title available?)
- scientific article; zbMATH DE number 4170962 (Why is no real title available?)
- Sparse reliable graph backbones
- scientific article; zbMATH DE number 3939394 (Why is no real title available?)
- Maximizing the Mean Number of Communicating Vertex Pairs in Series-Parallel Networks
- Connectivity of finite anisotropic random graphs and directed graphs
- Extremal connectivity and vulnerability in graphs
- Sparse reliable graph backbones
- Optimally Reliable Graphs for Both Vertex and Edge Failures
- The structure of max ?-minm?+1 graphs used in the design of reliable networks
- Graphs with given connectivity properties
- Trade-offs between density and robustness in random interconnection graphs
- Short vertex disjoint paths and multiconnectivity in random graphs: reliable network computing
- Binary strings and reliability of path networks
- Linking-Centers and Reliable-Trees of a Network
- On designing a network to defend against random attacks of radius two
- scientific article; zbMATH DE number 795107 (Why is no real title available?)
- scientific article; zbMATH DE number 841614 (Why is no real title available?)
- Asymptotics for connectivity probability of graph with low reliable arcs
- A note on the 2-connectivity in one-dimensional ad hoc networks
- An infinite family of 2-connected graphs that have reliability factorisations
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3218162)