Alvarez-Miranda, E (Alvarez-Miranda, Eduardo);Candia-Vejar, A (Candia-Vejar, Alfredo).Univ Talca, Ind Management Dept, Talca, ChileThis 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 c(e) in a given interval [c(e)(-), c(e)(+)] while taking a risk (c(e)(+) - c(e))/(c(e)(+) - c(e)(-)) of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints. (C) 2009 Elsevier B.V. All rights reserved.