Reliability covering problems for hypergraphs (Q1968515): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Reliability covering problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Calculating <i>K</i>-Connectedness Reliability Using Steiner Bounds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Network transformations and bounding network reliability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On graphs with randomly deleted edges / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reliability of binary systems / rank | |||
Normal rank |
Revision as of 14:40, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reliability covering problems for hypergraphs |
scientific article |
Statements
Reliability covering problems for hypergraphs (English)
0 references
29 November 2000
0 references
Given is a hypergraph \(G=(V, E)\), multiple edges are enabled and each edge \(e_{i}\in E\) can be excluded with equal probability \(1-p.\) The values of a reliability polynomial \(\text{Pol}(G,p)\) determine the probability of covering the set of nodes \(V\) \ by nonexcluded edges. The problem of evaluation of \(\text{Pol}(G,p)\) is called the reliability covering problem (RCP). The values of a reliability polynomial \(\text{Pol}_{C}(G,p)\) determine the probability that the graph \(G \) is connected (despite edges can be excluded). The problem of evaluation of \(\text{Pol}_{C}(G,p)\) is called reliability connected-covering problem (RCCP). It is mentioned that the problems are NP-complete and narrowing the problems to sets of multigraphs does not lead to substantial simplification. The goal of the paper is to obtain effectively computed estimates of RCP and RCCP for the general case. The shift operations of the first and of the second kind are investigated for hypergraphs and it is proved that they do not increase reliability coefficients of RCP and RCCP. The shift operations enable us to transform an arbitrary hypergraph into a multiregular one. Then it is proved that for multiregular hypergraphs reliability polynomials can be effectively computed. An example of such computations for canonical hypergraphs is given. The RCP and RCCP problems provide a general model of reliability of connections for general networks.
0 references
reliability covering
0 references
hypergraph
0 references
multigraph
0 references
reliability polynomial
0 references
NP-complete
0 references
0 references