On complexity of reliable probabilistic networks
type: Item
instance of: scholarly article
title: On complexity of reliable probabilistic networks
zbMATH Open document ID: 0958.68127
author: A. M. Koptev
published in: Moscow University Computational Mathematics and Cybernetics
publication date: 2001-02-25T00:00:00Z
review text: Some non-oriented networks with \(m\) input poles and \(h\) output poles, i.e. the \((m,n)\)-poles networks, every edge of which belongs to one of the non-crossing classes \(K_1,\dots{}, K_l\) are considered. It is supposed that the every edge \(u\) of the classe \(K_i\), \(i\ni \{1,\dots{},l\}\) has a cost \(c(u)=c_i\), \(c_i>0\) and can be in a conducting state with the probability \(p(u)=p_i\) and in a non-conducting state with the probability \(q(u)=1-p(u)\) inspite of states of the other edges. Additionally it is supposed that every line connecting two vertex of the \( (m,h)\)-poles network \(S\) is considered as a conducting one if every edge of the line is in a conducting state. A complexity of the network is determined as a summary cost all of its edges. Some complexity estimates (including an asymptotic one for the \((1,1)\)-poles network) of a minimal cost network are obtained. Here it was taken into consideration that for any pair ''input-output'' the probability of existence of a conducting line between the input and the output is not less than a given number \(n\) \((0<n<1)\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 1569663
zbMATH Keywords: probabilistic networks
zbMATH Keywords: complexity
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1569663