Narrow Results

A stochastic-flow network in which nodes as well as arcs all have both capacity and cost attributes is studied. We evaluate the possibility that the maximum flow of the network is not less than a demand under the budget constraint. Such a possibility is in general called the system reliability. A minimal path, an order sequence of arcs & nodes from the source to the sink without cycles, is used to assign the flow to each component (arc or node). Based on minimal paths, an efficient algorithm is proposed to generate all (d, C)-MPs that are the minimal capacity vectors meeting the demand d and the budget C. The system reliability can then be calculated in terms of all (d, C)-MPs.

The integrity of a graph $G$ is defined as the minimum value of $\left|S\right|+m(G-S)$ taken over all $S\subseteq V(G)$, where $m(H)$ denotes the maximum cardinality of a component of graph $H$. In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity.