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 E3·log(V) algorithm: two parabolas meet at most 2 times, thus the numbers of crossings of all weight parabolas is E(E - 1) = O(E2). 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