The problem I've run into is the following:

We have a graph G in which the weights of its edges are upward parabolas varying in time. For each instant t, we could potentially calculate the Minimum Spanning Tree. Since parabolas are convex and *MST*(*t*) is a minimisation problem we can try to find the 'global' MST: from all the infinetely many times *t* choose the *MST*(*t*) with minimal weight.

I've found an *E*^{3}·*log*(*V*) algorithm: two parabolas meet at most 2 times, thus the numbers of crossings of all weight parabolas is *E*(*E* - 1) = *O*(*E*^{2}). At all times between two consecutive crossings the order of the edges is the same; therefore the MST will be the same. Thus, we can compute it using Kruskal in *O*(*E*·*logV*) and then minimize for the edges found in *O*(*V*).

Can you find a faster solution? [I don't know if it exists :) ]

Thank you!

You can probably shave one E by keeping your MST in a splay tree. Then you should be able to "swap" two edges in O(logn) time, so for each E^2 crossing you can check if the edge which becomes "better" should replace the edge which becomes "worse".

That should make it :) thanks!

I didn't know splay trees for dynamic trees, if someone is interested here is a link to the paper: Sleator & Tarjan 1983