Deterministic risk control for cost-effective network connections

This paper considers the minimum connection problem in networks with uncertain data. In such a network it is assumed that one can establish a link e by paying a cost ce in a given interval while taking a risk of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints.