Imposing edges in Minimum Spanning Tree

Nicolas Isoart, Jean-Charles Régin

We are interested in the consequences of imposing edges in $T$ a minimum spanning tree. We prove that the sum of the replacement costs in $T$ of the imposed edges is a lower bounds…