Reliability covering problems for hypergraphs
type: Item
instance of: scholarly article
title: Reliability covering problems for hypergraphs
zbMATH Open document ID: 0949.05057
DOI: 10.1007/BF02667919
author: A. A. Chernyak
published in: Cybernetics and Systems Analysis
publication date: 2000-11-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1418918
zbMATH Keywords: reliability covering
zbMATH Keywords: hypergraph
zbMATH Keywords: multigraph
zbMATH Keywords: reliability polynomial
zbMATH Keywords: NP-complete
reviewed by: Adam Kapralski
MaRDI profile type: Publication
cites work: Reliability covering problems
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Calculating K-Connectedness Reliability Using Steiner Bounds
cites work: Network transformations and bounding network reliability
cites work: On graphs with randomly deleted edges
cites work: Reliability of binary systems
full work available at URL: https://doi.org/10.1007/bf02667919
OpenAlex ID: W2086673967
description: scientific article; zbMATH DE number 1418918