AbstractMany bounds for the all‐terminal reliability of computer networks have been proposed. Of those computable in polynomial time, the Ball‐Provan bounds and the Lomonosov Polesskii bounds provide the tightest estimates. A strategy is developed here using linear programming to obtain bounds which are tighter than both the Lomonosov‐Polesskii and the Ball‐Provan bounds. Computational results on these new bounds are also r