RestingRajarshi's blog

By RestingRajarshi, history, 4 years ago, In English

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)

  • Vote: I like it
  • +32
  • Vote: I do not like it

4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

In practice, sqrt decomposition works on many online problems, especially when the optimal approach has a large constant.