Parametric and kinetic minimum spanning trees
Parametric and kinetic minimum spanning trees
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree …