I have been searching for examples of usage of online Minimum Spanning Trees, but everything seems to be using the static minimum spanning tree and then some processing. Is there any actual use case of online MST finding, apart from just the purely theoretical aspect of it? (and except CP probs obvio).
Update: Clustering algorithms seems to be one such use case.
(Ill add to this if I find anything more, others please comment too if you know of any)
In practice, sqrt decomposition works on many online problems, especially when the optimal approach has a large constant.
hi, just pm'd you, hopefully that's not a problem :)