Can anyone think of a way to modify Kruskal's algorithm for a minimum spanning tree so that it must include a certain edge (u,v)?
I might be confusing, but as far as I remember, kruskal can handle negative weights,so you can give this edge -infinity weight.
-infinity, but a number low enough
to be significant enough that it cannot be ignored, something like -1 * sigma(|weight(e)|) for each e in E.